LeetCode 206. Reverse Linked List

題目

Reverse a singly linked list.

翻譯

反轉一個連結串列。

範例： { val:1, next: {val:2, next:null} } }

反轉： { val:2, next: {val:1, next:null} } }

思路

反轉一個連結陣列，需要一個指標來操作連結陣列，找出指標前的陣列並且將這個陣列加到目前指標節點的位置，這時候指標向前。

例如連結head[3,2,1]

1. 指標一開始放在[2]的位置，第一步將指標前的[3]從連結中切出來然後加到[2]的後面，連結陣列變成[3,2,1]。
2. 接下來指標向後移動到[1]，切出前面的[2,3]應且加到[1]之後，連結陣列變成[1,2,3]
3. 指標在往後移，發現後面已經沒有節點，交換完成。

解題

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head){
        return null;
    }

    if(!head.next){
        return head;
    }

    var prev = head;
    var cur  = head.next;
    prev.next = null;

    while(cur != null){
        var temp = cur;   // 用temp來操作目前的node
        cur = cur.next;   // 目前的node指標先往下，不然會被後面的操作影養

        // 這邊其實是兩個步驟
        // 我們只需要當前node的值，不需要他的next，temp.next = null
        // 將之前的linked list加到當前node後面  ， temp.next = prev
        temp.next = prev; 

        // 交換完成的temp變成新的prev
        prev = temp;
    }
    return prev;
};

* 給一個linked list = [1,2,3,4]。 執行while前，prev = head = [1,2,3,4] ;  cur  = head.next = [2,3,4] 
* 來看看prev，我們只需要[1]，後面的[2,3,4]都必須移除，prev.next=null，prev = [1]
* 第一次進入while， temp = cur = [2,3,4]。 這時候要讓cur指向[3,4]，不然對temp的操作也會影響到cur
* 這邊我們需要只留下[2]而不是[2,3,4]，temp.next = null ； temp = [2] 
* 將prev接到temp後面，temp.next = prev； temp = [2,1]； cur = [3,4]
* 交換完成，temp變成新的prev，prev = temp， prev = [2,1]
* 重複以上步驟，值到反轉完成。