206. Reverse Linked List

Leetcode Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

分析

这里使用三种方法，都是可以通过的。

1. 栈： 将链表节点依次放入栈，然后依次取出并连接，非常慢。
2. 利用迭代，依次获取后面的反转链表，然后将反转链表指向该元素，比较慢。
3. 将后面的元素依次与前面的元素连接起来，这种方法最快。

使用栈反转链表

public ListNode ReverseList(ListNode head) {
    if ((head == null) || (head.next == null)) return head;
    // 获得节点
    Stack<ListNode> stack = new Stack<>();
    while (head.next != null) {
        stack.push(head);
        head = head.next;
    }

    // 后面的节点指向前面的节点
    ListNode res = head;
    while (!stack.isEmpty()) {
        head.next = stack.pop();
        head = head.next;
    }
    // 尾部设置为null
    head.next = null;
    return res;
}

类似于1，只不过将栈表示为函数调用栈：

public ListNode ReverseList(ListNode head) {
    // base case
    if ((head == null) || (head.next == null)) return head;

    // 反转后面的节点
    ListNode res = ReverseList(head.next);
    // 反转第1个节点
    head.next.next = head;
    // 尾部设置为null
    head.next = null;
    return res;
}

将前面节点存储起来，让当前节点指向前面节点。

如果把当前节点$i$指向前一个节点$h$，会导致无法找到下一个节点$j$，所以需要将下一个节点$j$、前一个节点$i$保存起来。

/**
 * While you are traversing the list,
 * change the current node's next pointer to point to its previous element.
 * Since a node does not have reference to its previous node,
 * you must store its previous element beforehand.
 * You also need another pointer to store the next node before changing the reference.
 * Do not forget to return the new head reference at the end!
 */
public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode cur = head.next;       // 当前节点
    ListNode prev = head;           // 前面节点
    ListNode next;                  // 下一个节点

    while (cur.next != null) {
        // 反转当前节点和前一个节点： 将当前节点指向前一个节点
        next = cur.next;            // 保存下一个节点，备用
        cur.next = prev;            // 反转
        prev = cur;                 // 保存前一个节点，备用   
        cur = next;                 // 更新当前节点
    }
    // 反转最后一个节点
    cur.next = prev;

    // 设置链表末尾
    head.next = null;
    return cur;
}

也可以将后面的后面的节点存储起来，将后面的节点指向当前节点。含义完全和上述方法相同。

public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode cur = head, next = cur.next, nextNext;
    while (next != null) {
        nextNext = next.next;
        // 将头部节点的下一个节点设为null
        if (cur == head) cur.next = null;
        next.next = cur;
        cur = next;
        next = nextNext;
    }
    return cur;
}