# Swap Nodes in Pairs

## 解題流程

### 1. 釐清input, output
- input 為 `ListNode` (linked list)
- output 為 `ListNode` (經過兩兩成對反轉後的linked list)

(e.g. 若input為: `1 -> 2 -> 3 -> 4`，則output為: `2 -> 1 -> 4 -> 3`)

### 2. 列出constraints與edge cases
- constraints: 嘗試達到時間複雜度 O(n)，n為`ListNode`數量，空間複雜度 O(1)
- edge cases:
1. 空的linked list，應回傳`null`/`undefined`
2. 奇數個節點的linked list
- input為: `1`，則output亦為：`1`
- input為: `1 -> 2 -> 3`，則output應為： `2 -> 1 -> 3`

### 3. 解題思路

觀察到linked list是兩兩成對反轉，試著divie and conquer，先從第一對的反轉著手：

- **step1.** 將 `2` 指向 `1`， `1` 指向 `3`

原本:
`1 -> 2 -> 3 -> 4 -> 5 -> 6`
結果:
`2 -> 1 -> 3 -> 4 -> 5 -> 6`

- **step2.** 將 `1` 指向 `4`

原本：
`2 -> 1 -> 3 -> 4 -> 5 -> 6`

結果：

  2 -> 1
       |
       V
  3 -> 4 -> 5 -> 6            

這時候發現 `3 -> 4 -> 5 -> 6` 跟原本 `1 -> 2 -> 3 -> 4` 是一樣的pattern。

- 接下來執行像 **step1.** 一樣的操作， `4` 要指向 `3`， `3` 指向 `5`。
原本：

  2 -> 1
       |
       V
  3 -> 4 -> 5 -> 6            

結果：
`2 -> 1 -> 4 -> 3 -> 5 -> 6`

- 再來執行像 **step2.** 一樣的操作， `3` 要指向 `6`
原本：
`2 -> 1 -> 4 -> 3 -> 5 -> 6`

結果：

  2 -> 1 -> 4 -> 3
                 |
                 V
            5 -> 6 -> 7 -> 8            

- 到這邊已經觀察到相同pattern的出現，基本上就是重複**step1.** 跟 **step2.** 的操作，直到遇上`null`/`undefined`的`ListNode`。
- 接著將這樣的操作過程用程式碼寫出來。

### 4. 程式碼

- 初步寫出來會是這樣：

let first = head;
let second = head?.next;
let third = second?.next;
let fourth = third?.next;


while (first != null && second != null) {
  // step1.
  second.next = first; // 將 2 指向 1 
  first.next = third; // 將 1 指向 3

  // 如果4是空的時候，1繼續指向3(這個情形是奇數個節點的linked list)
  if (fourth != null) {
    // step2.
    first.next = fourth; // 將 1 指向 4
  }

  first = third;
  second = fourth;
  third = second?.next;
  fourth = third?.next;
}
    

- 但會有一個問題，最後必須回傳linked list的head，目前程式碼沒有處理到這件事。於是增加第8.行跟第24.行：

let first = head;
let second = head?.next;
let third = second?.next;
let fourth = third?.next;

// 因為經過翻轉，所以新的head會是原本第二個節點，不是原本第一個節點
// 但如果linked list只有一個節點的話，新的head一樣會是原本的第一個節點
let newHead = second ?? first; 

while (first != null && second != null) {
  second.next = first; 
  first.next = third; 

  if (fourth != null) {
    first.next = fourth; 
  }
      
  first = third;
  second = fourth;
  third = second?.next;
  fourth = third?.next;
}

return newHead;

- 最後leetcode上的程式碼長這樣：

var swapPairs = function(head) {
  let first = head;
  let second = head?.next;
  let third = second?.next;
  let fourth = third?.next;

  let newHead = second ?? first; 

  while (first != null && second != null) {
    second.next = first; 
    first.next = third; 
      
    if (fourth != null) {
      first.next = fourth; 
    }
      
    first = third;
    second = fourth;
    third = second?.next;
    fourth = third?.next;
  }

  return newHead;
}

### 5. 驗證
- leetcode測試通過，且 [edge cases](#2.-列出constraints與edge-cases) 有過關。
- 時間複雜度為O(n)：因為單個節點只會被操作constant的次數
- 空間複雜度為O(1)：因為並沒有額外建立反映linked list大小的記憶體