LeetCode 24. Swap Nodes in Pairs

題目

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

翻譯

給一個連結陣列，交換兩兩相鄰的節點並且回傳。

範例： 1->2->3->4, return 2->1->4->3。

你的演算法不能改變節點裡面的值，只能把節點搬來搬去。

思路一

先不管最後一條規則，也就是直接改變節點裡面值

1. 用prev表示前面的節點，cur表示後面的節點，跟一般交換的寫法一樣，先用一個temp儲存prev的值
2. 將cur的值塞給prev，然後再將temp的值塞給cur就完成交換
3. prev與cur尋找下一對node，繼續交換到結束

解題

改變node內的值

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

    while(prev != null && cur != null){
        // 很一般的交換
        var temp = prev.val;
        prev.val = cur.val;
        cur.val = temp;

        if(cur.next == null || cur.next.next == null) break;
        // 處理下一對node
        prev = cur.next;
        cur  = cur.next.next;     
    }   
    return head;
};

思路二

1. 題目要求不能改變節點裡面的值，所以node.val這種寫法應該是不行的
2. 首先先弄一個不動的首節點firstNode，後面節點移來移去時才不會受影響
3. 以[1,2,3,4]，一開始要交換的為[1.2]，因此需要先儲存[3,4]稍後再處理(下圖1)
4. 儲存後將list要處理的部分[1,2]跟不處理的部分[3,4]切開 (下圖2)，切開的同時讓[2]的next指向[1]
5. 將前一個節點prev的next指向[2]，因為[2]的next已經指向[1]，因此這邊已經完成[1,2] -> [2,1]的步驟
6. 接下來把之前儲存的[3,4]接到[1]後面，就可以繼續處理[3,4] ```

不改動node內的值

var swapPairs = function(head) { if(head == null || head.next == null) return head;

var firstNode = new ListNode(0);

firstNode.next = head;
var cur = head;
var prev = firstNode;
// 圖1的部分，目前處理的節點cur，前一個節點prev

var nextKeep; // 預備用來儲存後面未處理的節點

while (cur!=null && cur.next!=null){
    nextKeep = cur.next.next; //圖1，相將後面的節點[3,4]儲存起來
    cur.next.next = cur; //圖2，將[1,2]與[3,4]斷開，這時候[2]的next已經變成[1]      
    // 圖3將prev的next指向[2]，注意這時候[2]的next已經指向[1]，整理一下其實如圖4
    prev.next = cur.next;

    //圖5，將[3,4]接回[1]
    cur.next = nextKeep;

    //處理下一組
    prev = cur;
    cur = cur.next;        
}
return firstNode.next;

} ```

圖解不改動node值的寫法