Contents

[Golang][Leetcode][linkedList]刷題系列-24-Swap Nodes


24. Swap Nodes in Pairs


Level : Medium

原題連結 : Click

題目 :

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

Input: head = [1,2,3,4]

Output: [2,1,4,3]


Input: head = []

Output: []


Input: head = [1]

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解法 :

  1. 首先我們需要一個dummyHead,因為需要一個三個pointer在走的時候,head的位置會變動,所以我們已dummyHead.Next作為回傳值
  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
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!