Contents

# 24. Swap Nodes in Pairs

## 題目 :

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

### Example :

Note

Output: [2,1,4,3]

Output: []

Output: [1]

#### 解題思路 :

• 這題我最直觀的想法會覺得可以直接traversal，然後設兩個pointer然後node兩兩交換
• 但要注意的就是當一次處理兩個pointer但它牽涉到的不只兩個node
• 假設兩node a && node b = a.Next，當兩個交換後，變成a = b.Next，那假設原本有個指向 a 的 c 就亂掉，需要改成c.Next = b
• 故需要三個pointer去操作
• 然後可以寫成Iterative or recursive的解法

Iterative解法 :

2. 由於題目例子敘述，當只有0個或1個node並未滿足pair時，或當剩1個node無法再形成pair時，就是回傳
3. 所以假設順序是dummy -> 1 -> 2 -> 3 -> 4 -> 5
4. 先將pre = dummy , head = 1
5. 1跟2要交換位置所以
• step 1: pre.Next = head.Next (dummy -> 2)
• step 2: next := head.Next.Next (next = 3)
• step 3: pre.Next.Next = head (2 -> 1)
• step 4: head.Next = next (1 -> 3)
• 變成 dummy -> 2 -> 1 -> 3
• 最後另 pre = head (1的位置) , head = next (3的位置) 進入下一個loop

### 以下是我自己的解法 - time complexity: O(n) , space complexity: O(1)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Swap Nodes in Pairs.

Iterative version

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 `````` ``````/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func swapPairs(head *ListNode) *ListNode { dummyHead := &ListNode{ Next: head, } pre := dummyHead for head != nil && head.Next != nil{ pre.Next = head.Next next := head.Next.Next pre.Next.Next = head head.Next = next pre = head head = next } return dummyHead.Next } ``````

recursive version

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 `````` ``````/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func swapPairs(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } next := head.Next head.Next = swapPairs(next.Next) next.Next = head return next } ``````