未分類

Swap Nodes in Pairs

Go, LeetCode, LinkedList

Swap Nodes in Pairs

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

For example:

1
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.

提示 解題應用
LinkedList Pointer

Default:

1
2
3
4
5
6
7
8
9
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
}

解答思路:

由於不會太複雜，所以很快就想好了大概，在這邊會發現到一定是前後兩個一組湊一組交換，那麼其實只要設一個計數器只要是偶數就只與前交換，或者是只要是基數就只與後交換，如此一來就搞定了，不過這邊有一點要注意到就是每組之間的聯繫，如果下一組只有一個那當然只要接上就好，但如果是兩個勢必會做交換，這時前一組要接續的下一個節點就會是交換前原本在後面的節點，只要有注意到這回事應該沒有什麼大問題。

程式碼解說:

一開始簡單的判斷一下是不是有兩個以上，如果只有一個就只要回傳第一個位置就好，但如果有兩個以上就要傳第二個的位置，畢竟會交換跑至開頭的位置，這邊會發現這次沒有做頭節點，因為不會在第一個節點做刪除或在其之前做插入，所以就不須理會一致性的操作。

1
2
3
4
5
6
var top *ListNode
if head != nil && head.Next != nil {
	top = head.Next
} else {
	top = head
}

再來只要依續存取節點，同時用一變數來記錄前一節點的位置以方便後續操作，這邊我把計數除以2取餘數來取得為奇數的索引，接著便是前後節點交換，這邊要注意head因為要繼續往下走其它節點，所以交換完之後記得要把head指向交換前原本在前面的節點，如此一來交換後節點到了後頭便能繼續再往下走，才不會發生同一點重覆操作的狀況，最後只要知道下一組也就是下一個節點與下下個節點存不存在，便能知道下一組會不會交換，來判斷前一組的節點要不要指向下一組交換前後頭的節點。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var tmp *ListNode
var count int
for head != nil {
	count++
	tmp = head
	head = head.Next
	if head != nil && count%2 != 0 {
		tmp.Next = head.Next
		head.Next = tmp
		head = tmp
	} else if head != nil && head.Next != nil {
		tmp.Next = head.Next
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func swapPairs(head *ListNode) *ListNode {
	var top *ListNode
	var tmp *ListNode
	var count int
	if head != nil && head.Next != nil {
		top = head.Next
	} else {
		top = head
	}
	for head != nil {
		count++
		tmp = head
		head = head.Next
		if head != nil && count%2 != 0 {
			tmp.Next = head.Next
			head.Next = tmp
			head = tmp
		} else if head != nil && head.Next != nil {
			tmp.Next = head.Next
		}
	}
	return top
}

總結:

LinkedList做前後兩個為一組交換可以簡易的用計數來分組並操作，若下一個接續的組中只剩一個便直接接上即可，但若是兩個便要注意前一組所接續的下一個節點便是在交換前原本在後面的節點。

分享到