【算法】009、单双链表反转-EW帮帮网

文章目录

一、单链表反转
- 1.1 实现思路
- 1.2 多语言解法
二、双链表反转
- 2.1 实现思路
- 2.2 多语言解法

一、单链表反转

1.1 实现思路

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

// go
package main

import "fmt"

// single
type Node struct {
	val  int
	next *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 = b
	b.next = c
	return 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 = nil
	return n
}

func reverse(head *Node) *Node {
	if head == nil {
		return nil
	}
	var pre *Node = nil
	var next *Node = nil
	for head != nil {
		next = head.next // 备份 head.next, 因为下一行就要改其指向了
		head.next = pre  // 反转的关键, 指针方向变了, 原来 head.next 指向 next, 现在 head.next 指向 pre
		pre = head       // 向后迭代
		head = next      // 同上
	}
	return pre
}

1.2 多语言解法

$Cpp / G o / P y t h o n / R u s t / J s / T s$

// 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 = v
        self.next = n


def la():
    c = Node(2, None)
    b = Node(1, c)
    a = Node(0, b)
    return a


def laCheck(n):
    ans = []
    while n:
        ans.append(n.val)
        n = n.next
    if ans != [2, 1, 0]:
        raise ValueError


def lb():
    return Node(5, None)


def reverse(head):
    pre = None
    next = None
    while head:
        next = head.next
        head.next = pre
        pre = head
        head = next
    return pre


def 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 main

func 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  int
	pre  *Node
	next *Node
}

func la() *Node {
	c := &Node{2, nil, nil}
	b := &Node{1, nil, c}
	a := &Node{0, nil, b}

	c.pre = b
	b.pre = a
	return a
}

func laCheck(h *Node) {
	ans := []int{}
	iter := h
	for 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 := h
	for 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 = nil
	iter := h
	for iter != nil {
		next := iter.next
		iter.next = pre
		iter.pre = next
		pre = iter
		iter = next
	}
	return pre
}

2.2 多语言解法

$Cpp / G o / P y t h o n / R u s t / J s / T s$

#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 = None
    r = reverse(l)
    if r is not None:
        raise Exception("error")

    print("ok")


class Node(object):
    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None

def la():
    c=Node(2)
    b=Node(1)
    a=Node(0)
    
    a.next = b
    b.next = c
    
    c.pre = b
    b.pre = a
    
    return a

def la_check(h):
    ans = []
    cur = h
    while cur:
        ans.append(cur.val)
        cur = cur.next
    if 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 = None
    cur = h
    while cur:
        next = cur.next
        cur.next = pre
        cur.pre = next
        pre = cur
        cur = next
    return pre

if __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 = h
    while (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 = iter
        iter = next
    }
    return prev
}


main();

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

文章目录

一、单链表反转

1.1 实现思路

1.2 多语言解法

二、双链表反转

2.1 实现思路

2.2 多语言解法

网站公告

今日签到

热门文章

最新发布