Problem

Reverse a linked list.

Example
For linked list 1->2->3, the reversed linked list is 3->2->1

思路一(iterative)

• 两个指针, prev和curt, 是curt指向prev, 然后更新curt至下一个
• 最后curt变成空, 返回prev

    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }

思路二(recursive)

• 假设子问题完成, 并返回末节点
• 当前节点需要连上上一个节点

    public ListNode reverseList(ListNode head) {
        return reverseList(head, null);
    }

    private ListNode reverseList(ListNode head, ListNode prev) {
        if (head == null) return prev;
        ListNode next =  head.next;
        head.next = prev;

        return reverseList(next, head);
    }