Reverse Linked List

• Easy
• keyword: Recursion
• 类似: Tree, invert Binary Tree

Reverse a singly linked list.

2个思路:

1. 递推
2. 递归

   图示如下:

idea1:

• 经典的题目啊, 就是和swap差不多, 只是这里swap的是pointer.
• 思路要清晰: 如下图所示, 由于每次将cur的next指向pre, 所以post要保存起来, 并将pre/cur移到下一对. 这里的pre初始化为null, 因为这也是有效的逆序链表的表头(最简单形态).
• 代码如下:

public ListNode reverse(ListNode head) {
    ListNode pre = null;
    while (head != null) {
        ListNode post = head.next;
        head.next = pre;
        pre = head;
        head = post;
    }
    return pre;
}

idea2:

• 很经典的recursion写法, recursion的作用是将所有recursive call暂存于stack里面, 知道bottom再一个个从stack里面pop出来walk-down tree的过程.
• 其实这个和invert Binary Tree, 或者N-ary tree to Binary Tree是一样的.
• 代码如下:

public ListNode reverse(ListNode head) {
    if (head == null)  return null;
    if (head.next == null)  return head;
    ListNode newHead = reverse(head.next);  // 在当前层(想成tree/graph)的时候, 将下一层翻转了.
    head.next.next = head;  // 注意: 正是因为recursion将walk down的过程保存在stack里面了, 所以应该是bottom-up的过程中反转当前层.
    head.next = null;  // 记得不要有cycle.
    return newHead;  // 这个指向定值: 最后一个node.
}