【LeetCode】 206. 反轉連結清單 Java版

206. 反轉連結清單

反轉一個單連結清單。

示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

解決思路：

1. 需要定義四個節點；

• 為了解決反轉目前節點的時候找不到前驅節點，那我們就需要一個節點來儲存目前節點的前驅節點；
• 同時定義cur表示目前反轉的節點；
• curNext是下一個需要反轉的節點，需要注意，cur不為空的時候才有curNext,否則就會空指針異常；
• 最最最重要的是要把反轉後的新連結清單的頭節點存起來，就是newHead;

1. 反轉的思路是:

• 反轉節點的next指向前驅節點；

  cur.next = prev;

• 前驅節點往後移；

  prev = cur;

• 反轉的節點往後移；

  cur = curNext;

1. 如果在反轉的過程中cur.next == null;那麼就找到新的頭節點了，記得儲存。

   

public ListNode reverseList(ListNode head) {
        //定義四個節點，cur不為空的時候再定義curNext
        ListNode prev = null;
        ListNode cur = head;
        ListNode newHead = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            //如果cur.next == null，就是新的頭節點，儲存下來
            if (cur.next == null) {
                newHead = cur;
            }
            cur.next = prev;//先把cur.next指向先驅
            prev = cur;//先驅挪到後面一個
            cur = curNext;//cur也往後挪一個

        }
         return newHead;
    }