206. Reverse 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?

M1: iterative

需要两个指针prev, cur。注意循环的终止条件是cur == null，否则最后一个节点和之前反转完成的链表接不上，当cur = null的时候，返回prev即可。在每一次循环里，先保存cur的下一个节点nextnode，cur指向prev，prev向前移动，cur也向前移动，直到cur == null。

time: O(n), space: O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode prev = null, cur = head;
        while(cur != null) {
            ListNode nextnode = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextnode;
        }
        return prev;
    }
}

M2: recursive

base case是当head == null或者head.next == null时返回head. 用一个新的node表示对head.next调用函数的返回值. 当recursion到base case的时候，head到达了最后一个节点（head就是最后需要返回的值），此时把head的下一个节点指向head，head指向null，返回至上一层recursion.

e.g. 当recursion到base case，即head.next == null时，返回head，注意此时是对head.next调用recursive函数，即head.next.next == null返回，用cur保存此时的返回值 (4)，而head此时在3的位置。head.next.next = head操作后，4指向3，head.next = null操作后，3指向null (原来指向4)。再回上一层，head在2，两步操作后，3->2；再回上一层，head在1，2->1。此时返回cur即可

1->2->3->4->null　　　　1->2->3<-4   null

           h   c　　　　　　　　　　 h    c

1->2<-3<-4    null　　　　1<-2<-3<-4   null

     h 　　  c　　　　　　　h              c

time: O(n), space: O(n) - store the return value in each recursive call

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}