Reverse Linked List

Question:

Reverse a linked list.

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

Challenge Reverse it in-place and in one-pass

Lesson Learned:

• // 错误的程序：

        /* ListNode cur = head;
         * ListNode top = head;
         * head = head.next;
         * cur.next = top;
         * 此时因为head一直有指针指着，所以head和head.next之间的link
         * 没有断，因此形成了一个infinite loop。
        */
  

• // 断掉Link的方法：.next=someNode; or .next = null

• // 让node飞走的方法：不再有reference指向这个node。

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        // write your code here
        if (head == null || head.next == null) {
            return head;
        }
        // while head has at least two elements

        ListNode top = null;


        while (head != null) {
            ListNode cur = head;
            head = head.next;
            cur.next = top;
            top = cur;
        }
        return top;
    }
}