206. Reverse Linked List (Easy)

Reverse a singly linked list.

Hint:

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

1->3->2->4
pre: null       1
cur: 1(head)
next: 3
cur.next: null

Solution 1: Iterative O(n); O(1)

3个指针：pre, cur, next

When traverse the list, change the current node's next pointer to point to its previous node.
Since a node does not have reference to its previous node, we must store its previous node beforehand.
We 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) {
        // null->1->2->3->4->5->null
        //  p    c
        ListNode pre = null;
        ListNode cur = head;
        while(cur !=null){
            // null->1->2->3->4->5->null
            //  p    c  n
            ListNode next = cur.next; //cur.next will be null when cur is the last node

            // null<-1  2->3->4->5->null
            //  p    c  n
            cur.next = pre;

            // null<-1  2->3->4->5->null
            //       c  n
            //       p
            pre = cur;

            // null<-1  2->3->4->5->null
            //       p  n
            //          c
            cur = next;
        }
        // null<-1<-2<-3<-4<-5  null
        //                   p  n
        //                      c

        //ListNode newHead = pre; //如果要直接输出，加上这块代码
        // while (newHead != null) {
        // System.out.print(newHead.val + " ");
        // newHead = newHead.next;
        // }
        return pre;
    }

Solution 2: Recursive O(n); O(n)

1->2->3->4, 1->2->3<-4

比如1->2->3这个最简单的链表，第一层时p指向1，head指向对2调用递归对结果，在第二层中，p指向2，head指向对3调用递归，此时递归返回3，所以第二层的head指向3，那么p->next->next=p的操作就把2连到了3的后面，而p->next=NULL这一步是要把2后面断开，因为刚开始2后面连的是3，我们翻转后就不能这么连了。。。你再感受一下。。。

The recursive method is to work backwards and we need to find the recurrence relation. Assume that the rest of the list had already been reversed, now we need to reverse the front part. For example, if current node is 2, it's right part has been reversed. We let node 3 to point to 2 and we need to let current node's next pointer point to null.
Return new head, which is the last node of original node all the way.

    public ListNode reverseList(ListNode cur) {
        //cur == null是为了检查输入节点是null的corner case
        //cur.next == null是递归的出口，即当前节点是原链表的最后一个节点
        if (cur == null || cur.next == null) {
            return cur;
        }
        //下面这行代码必须放在递推关系前面，因为要先遍历到最后一个节点。
        ListNode newHead = reverseList(cur.next); //newHead一直是原链表的最后一个节点
        cur.next.next = cur; //let next node point to current node，1->2 to 1<=>2
        cur.next = null; //important! let current node's next pointer point to null, 1<=>2 to 1<-2
        //因为是递归，不能让next pointer直接指向前面一个节点。
        return newHead;
    }

Solution 3: Iterative with stack O(n); O(n)

    public ListNode reverseList(ListNode head) { 
        Stack<ListNode> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (!stack.empty()) {
            ListNode temp = stack.pop();
            temp.next = null; //must let temp'next point to null.
            cur.next = temp;
            cur = cur.next;
        }
        return dummy.next;
    }

Follow Up:

1.如果是一个有环的链表怎么办？？？

2.how to do it without change pointer

    /**
     * Recursive with two pointers
     */
    ListNode left = null;
    boolean meet = false;

    public ListNode reverseListG(ListNode head) {
        if (head == null || head.next == null) return head;
        left = head;
        meet = false;
        helper(head);
        return head;
    }

    public ListNode helper(ListNode head) {
        if (head.next == null) return head;

        ListNode right = helper(head.next);
        if (!meet) {
            int tmp = left.val;
            left.val = right.val;
            right.val = tmp;
            if (left == right || left.next == right) meet = true;
            left = left.next;
        }
        return head;
    }