蒙国造博客

反转单向链表

以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;
    }
}

该方法的时间复杂度是O(n),空间复杂度是O(1)

 

 

退出移动版