【算法】009、单双链表反转

【算法】009、单双链表反转

一、单链表反转

1.1 实现思路

维护 pre 变量。
从前向后遍历 head，首先记录 next = head.next，其次反转指针使 head.next = pre. 再向后迭代使 pre = head，head = next。
直到遍历完 head == nil 为止。最终 pre 就是原链表的尾节点（即新链表的头节点），返回 pre 即可。

// go
package mainimport "fmt"// single
type Node struct {val  intnext *Node
}func main() {la := la()laCheck(reverse(la))lb := lb()if reverse(lb) != lb {panic("error for lb")}lnil := lnil()if reverse(lnil) != nil {panic("error for nil")}print("ok")
}func la() *Node {a := &Node{val: 0}b := &Node{val: 1}c := &Node{val: 2}a.next = bb.next = creturn a
}func laCheck(h *Node) error {ans := make([]int, 0)for iter := h; iter != nil; iter = iter.next {ans = append(ans, iter.val)}if len(ans) != 3 {return fmt.Errorf("err len")}if ans[0] != 3 {return fmt.Errorf("err val")}if ans[1] != 1 {return fmt.Errorf("err val")}if ans[2] != 0 {return fmt.Errorf("err val")}return nil
}func lb() *Node {return &Node{val: 5, next: nil}
}func lnil() *Node {var n *Node = nilreturn n
}func reverse(head *Node) *Node {if head == nil {return nil}var pre *Node = nilvar next *Node = nilfor head != nil {next = head.next // 备份 head.next, 因为下一行就要改其指向了head.next = pre  // 反转的关键, 指针方向变了, 原来 head.next 指向 next, 现在 head.next 指向 prepre = head       // 向后迭代head = next      // 同上}return pre
}

1.2 多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;
struct Node
{int val;Node *next;
};Node *la()
{Node *c = new Node{2, nullptr};Node *b = new Node{1, c};Node *a = new Node{0, b};return a;
}void laCheck(Node *head)
{vector<int> ans;Node *iter = head;while (iter != nullptr){ans.push_back(iter->val);iter = iter->next;}if (ans.size() != 3){throw runtime_error("length error");}if (ans[0] != 2){throw runtime_error("0 error");}if (ans[1] != 1){throw runtime_error("1 error");}if (ans[2] != 0){throw runtime_error("2 error");}
}Node *lb()
{return new Node{5, nullptr};
}void lbCheck(Node *head)
{vector<int> ans;Node *iter = head;while (iter){ans.push_back(iter->val);iter = iter->next;}if (ans.size() != 1){throw runtime_error("length error");}if (ans[0] != 5){throw runtime_error("5 error");}
}Node *lnone()
{return nullptr;
}Node *reverse(Node *head)
{Node *pre = nullptr;Node *iter = head;while (iter){Node *next = iter->next;iter->next = pre;pre = iter;iter = next;}return pre;
}int main()
{Node *l = la();Node *r = reverse(l);laCheck(r);l = lb();r = reverse(l);lbCheck(r);l = lnone();r = reverse(l);if (r != nullptr){throw runtime_error("error for lnone");}cout << "ok" << endl;
}

// go 同上

# python
class Node(object):def __init__(self, v, n):self.val = vself.next = ndef la():c = Node(2, None)b = Node(1, c)a = Node(0, b)return adef laCheck(n):ans = []while n:ans.append(n.val)n = n.nextif ans != [2, 1, 0]:raise ValueErrordef lb():return Node(5, None)def reverse(head):pre = Nonenext = Nonewhile head:next = head.nexthead.next = prepre = headhead = nextreturn predef main():l = la()l = reverse(l)laCheck(l)l = lb()if reverse(l) != l:raise ValueError(123)if reverse(None) != None:raise ValueError(111)print("ok")if __name__ == "__main__":main()

// rust
fn main() {let l = la();let r = reverse(l);la_check(r).expect("la_check");let l = lb();let r = reverse(l);lb_check(r).expect("lb_check");let l = lnone();let r = reverse(l);if r.is_some() {panic!("lnone");}println!("ok")
}#[derive(Debug)]
struct Node {val: i32,next: Option<Box<Node>>,
}impl Node {fn new(val: i32, next: Option<Box<Node>>) -> Self {Self { val, next }}
}fn la() -> Option<Box<Node>> {let c = Some(Box::new(Node::new(2, None)));let b = Some(Box::new(Node::new(1, c)));let a = Some(Box::new(Node::new(0, b)));a
}fn la_check(head: Option<Box<Node>>) -> Result<(), String> {let mut ans = vec![];let mut iter = head;while let Some(node) = iter {ans.push(node.val);iter = node.next;}if ans.len() != 3 {return Err("len".to_string());}if ans[0] != 2 {return Err("0".to_string());}if ans[1] != 1 {return Err("1".to_string());}if ans[2] != 0 {return Err("2".to_string());}Ok(())
}fn lb() -> Option<Box<Node>> {Some(Box::new(Node::new(5, None)))
}fn lb_check(head: Option<Box<Node>>) -> Result<(), String> {let mut ans = vec![];let mut head = head;while let Some(node) = head {ans.push(node.val);head = node.next;}if ans.len() != 1 {return Err("len".to_string());}if ans[0] != 5 {return Err("5".to_string());}Ok(())
}fn lnone() -> Option<Box<Node>> {None
}fn reverse(head: Option<Box<Node>>) -> Option<Box<Node>> {let mut head = head;let mut pre: Option<Box<Node>> = None;while let Some(mut node) = head {let next = node.next.take();node.next = pre;pre = Some(node);head = next;}pre
}

// js

// ts
function main() {let l = la();let r = reverse(l);laCheck(r);l = lb();r = reverse(l);lbCheck(r);l = lnone();r = reverse(l);if (r) {throw new Error("lnone");}console.log("ok");
}class ListNode {val: number;next: ListNode | null;constructor(val: number, next: ListNode | null) {this.val = val;this.next = next;}
}function la(): ListNode | null {const c = new ListNode(2, null);const b = new ListNode(1, c);const a = new ListNode(0, b);return a;
}function laCheck(head: ListNode | null) {const ans: number[] = [];let iter: ListNode | null = head;while (iter) {ans.push(iter.val);iter = iter.next;}if (ans.length !== 3) {throw new Error("length");}if (ans[0] !== 2) {throw new Error("0")}if (ans[1] !== 1) {throw new Error("1");}if (ans[2] !== 0) {throw new Error("2");}
}function lb(): ListNode {return new ListNode(5, null);
}function lbCheck(head: ListNode | null) {const ans: number[] = [];let iter: ListNode | null = head;while (iter) {ans.push(iter.val);iter = iter.next;}if (ans.length !== 1) {throw new Error("length");}if (ans[0] !== 5) {throw new Error("5");}
}function lnone(): ListNode | null {return null;
}function reverse(head: ListNode | null): ListNode | null {let pre: ListNode | null = null;while (head) {const next = head.next;head.next = pre;pre = head;head = next;}return pre;
}main();

二、双链表反转

2.1 实现思路

和 单链表反转 相同，每次反转两个指针即可，即 head.next = pre 和 head.pre = next。

package mainfunc main() {l := la()r := reverse(l)laCheck(r)l = lb()r = reverse(l)lbCheck(r)r = reverse(nil)if r != nil {panic("lnil")}println("ok")
}type Node struct {val  intpre  *Nodenext *Node
}func la() *Node {c := &Node{2, nil, nil}b := &Node{1, nil, c}a := &Node{0, nil, b}c.pre = bb.pre = areturn a
}func laCheck(h *Node) {ans := []int{}iter := hfor iter != nil {ans = append(ans, iter.val)iter = iter.next}if len(ans) != 3 {panic("length is not 3")}if ans[0] != 2 {panic("0 is not the first element")}if ans[1] != 1 {panic("1 is not the second element")}if ans[2] != 0 {panic("2 is not the third element")}
}
func lbCheck(h *Node) {ans := []int{}iter := hfor iter != nil {ans = append(ans, iter.val)iter = iter.next}if len(ans) != 1 {panic("length is not 3")}if ans[0] != 5 {panic("0 is not the first element")}
}func lb() *Node {return &Node{5, nil, nil}
}func reverse(h *Node) *Node {var pre *Node = niliter := hfor iter != nil {next := iter.nextiter.next = preiter.pre = nextpre = iteriter = next}return pre
}

2.2 多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;class Node
{
public:int val;Node *pre;Node *next;Node() : val(0), pre(nullptr), next(nullptr) {}Node(int val) : val(val), pre(nullptr), next(nullptr) {}Node(int val, Node *pre, Node *next) : val(val), pre(pre), next(next) {}
};Node *la()
{Node *c = new Node(2);Node *b = new Node(1);Node *a = new Node(0);a->next = b;b->next = c;c->pre = b;b->pre = a;return a;
}void la_check(Node *h)
{vector<int> ans;Node *iter = h;while (iter){ans.push_back(iter->val);iter = iter->next;}if (ans.size() != 3){throw new runtime_error("size");}if (ans[0] != 2){throw new runtime_error("0");}if (ans[1] != 1){throw new runtime_error("1");}if (ans[2] != 0){throw new runtime_error("2");}
}Node *lb()
{return new Node(5);
}void lb_check(Node *h)
{if (h == nullptr){throw new runtime_error("h null");}if (h->val != 5){throw new runtime_error("val");}
}Node *reverse(Node *h)
{Node *pre = nullptr;Node *iter = h;while (iter){Node *next = iter->next;iter->next = pre;iter->pre = next;pre = iter;iter = next;}return pre;
}int main()
{Node *l = la();Node *r = reverse(l);la_check(r);Node *l2 = lb();Node *rb = reverse(l2);lb_check(rb);Node *lnull = nullptr;if (reverse(nullptr)){throw new runtime_error("lnull");}cout << "ok" << endl;
}

# python
def main():l = la()r = reverse(l)la_check(r)l = lb()r = reverse(l)lb_check(r)l = Noner = reverse(l)if r is not None:raise Exception("error")print("ok")class Node(object):def __init__(self, val):self.val = valself.pre = Noneself.next = Nonedef la():c=Node(2)b=Node(1)a=Node(0)a.next = bb.next = cc.pre = bb.pre = areturn adef la_check(h):ans = []cur = hwhile cur:ans.append(cur.val)cur = cur.nextif ans != [2,1,0]:raise Exception("error")def lb():return Node(5)def lb_check(h):if h.val != 5:raise Exception("error")if h.next is not None:raise Exception("error")if h.pre != None:raise Exception("error")def reverse(h):pre = Nonecur = hwhile cur:next = cur.nextcur.next = precur.pre = nextpre = curcur = nextreturn preif __name__ == "__main__":main()

// rust
use std::cell::RefCell;
use std::rc::Rc;#[derive(Debug)]
struct Node {val: i32,prev: Option<Rc<RefCell<Node>>>,next: Option<Rc<RefCell<Node>>>,
}impl Node {fn new(val: i32) -> Self {Node {val,prev: None,next: None,}}
}fn la() -> Option<Rc<RefCell<Node>>> {let c = Rc::new(RefCell::new(Node::new(2)));let b = Rc::new(RefCell::new(Node::new(1)));let a = Rc::new(RefCell::new(Node::new(0)));a.borrow_mut().next = Some(b.clone());b.borrow_mut().next = Some(c.clone());c.borrow_mut().prev = Some(b.clone());b.borrow_mut().prev = Some(a.clone());Some(a)
}fn la_check(h: Option<Rc<RefCell<Node>>>) {let mut iter = h;let mut ans = Vec::new();while let Some(node) = iter {ans.push(node.borrow().val);iter = node.borrow().next.clone();}if ans.len() != 3 {panic!("length is not 3");}if ans[0] != 2 {panic!("0 error");}if ans[1] != 1 {panic!("1 error");}if ans[2] != 0 {panic!("2 error");}
}fn lb() -> Option<Rc<RefCell<Node>>> {Some(Rc::new(RefCell::new(Node::new(5))))
}fn lb_check(h: Option<Rc<RefCell<Node>>>) {let mut iter = h;let mut ans = Vec::new();while let Some(node) = iter {ans.push(node.borrow().val);iter = node.borrow().next.clone();}if ans.len() != 1 {panic!("length is not 1");}if ans[0] != 5 {panic!("0 error");}
}fn reverse(h: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {let mut cur = h;let mut pre: Option<Rc<RefCell<Node>>> = None;while let Some(node) = cur {let next = node.borrow_mut().next.take();node.borrow_mut().next = pre;node.borrow_mut().prev = next.clone();pre = Some(node);cur = next}pre
}fn main() {let l = la();let r = reverse(l);la_check(r);let l = lb();let r = reverse(l);lb_check(r);let l: Option<Rc<RefCell<Node>>> = None;let r = reverse(l);if r.is_some() {panic!("r is not None");}println!("ok");
}

function main() {let l = la();let r = reverse(l);la_check(r);l = lb();r = reverse(l);lb_check(r);r = reverse(null);if (r) {throw new Error("lnull error")}console.log("ok")
}class ListNode {val: number;prev: ListNode | null;next: ListNode | null;constructor(val: number) {this.val = val;this.prev = null;this.next = null;}
}function la(): ListNode | null {const c = new ListNode(2);const b = new ListNode(1);const a = new ListNode(0);a.next = b;b.next = c;c.prev = b;b.prev = a;return a;
}function la_check(h: ListNode | null) {let ans: number[] = [];let iter: ListNode | null = hwhile (iter) {ans.push(iter.val);iter = iter.next;}if (ans.length != 3) {throw new Error("length error")}if (ans[0] != 2) {throw new Error("0 error")}if (ans[1] != 1) {throw new Error("1 error")}if (ans[2] != 0) {throw new Error("2 error")}
}function lb(): ListNode | null {return new ListNode(5);
}function lb_check(h: ListNode | null) {if (!h) {throw new Error("h null error")}if (h.val != 5) {throw new Error("5 error")}if (h.next) {throw new Error("next error")}if (h.prev) {throw new Error("prev error")}
}function reverse(h: ListNode | null): ListNode | null {let iter: ListNode | null = h;let prev: ListNode | null = null;while (iter) {let next = iter.next;iter.next = prev;iter.prev = next;prev = iteriter = next}return prev
}main();