反转单向链表

2 答案

Java实现代码:

public class Node {
    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }

    public Node reverseList(Node head) {
        Node prev = null;           // 用于暂存前面的节点
        Node next = null;           // 用于暂存后面的节点

        while (head != null) {
            next = head.next;       // 把后面的节点暂存起来
            head.next = prev;       // 当前节点的next就可以指向暂存的上一个节点,也即,反转节点指向

            prev = head;            // 把当前节点设置为上一个节点
            head = next;            // 设置下一个节点为当前节点
        }

        return prev;
    }
}
muzi muzi 1 年前 点赞 0 

Python实现:

class Node(object):
    def __init__(self):
        self.value = None
        self.next = None

def reverse_linked_list(head):
    if not head or not head.next:
        return head

    prev = None  # 用于暂存前面的节点
    next = None  # 用于暂存前面的节点
    while head:
        next = head.next  # 缓存当前节点的向后指针,待下次迭代用
        head.next = prev  # 这一步是反转的关键,相当于把当前的向前指针作为当前节点的向后指针
        prev = head  # 作为下次迭代时的(当前节点的)向前指针
        head = next  # 作为下次迭代时的(当前)节点

    return prev  # 返回头指针,头指针就是迭代到最后一次时的head变量(赋值给了pre)

muzi muzi 1 年前 点赞 0