未分類

Rotate List

Go, LeetCode, LinkedList, TwoPointers

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:

1
2
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
提示 解題應用
LinkedList Pointer
TwoPointers 紀錄index位置

Default:

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

解答思路:

因為向右移1格時從最後一個節點就會先跳躍至開頭，而右移k格時則倒數k個節點移動到開頭，因此只要知道倒數第k+1個節點的位置(與最後一個節點位置差k)，便能直接將後頭整串至底移動到開頭做嫁接，可以一口氣完成右移k格的旋轉，所以一開始就用兩變數指向頭的位置，先移動一指向變數遍歷LinkedList，待兩變數距離超過k時另一個指向變數才跟著向後遍歷，如此一來待後頭的指向變數到底時，前頭指向變數指到的位置就會是倒數第k+1個節點的位置，嫁接完就是我們要的結果了。

程式碼解說:

一開始先初始化兩個變數指向頭的位置，而count則表示後頭的變數位置(已經遍歷了多少個節點)，接下來就是開始尋找倒數第k個節點的位置，如果在後頭的變數本身指向的位置不為空且下一個要遍歷的位置也不為空才繼續向下遍歷同時將count+1，當後頭遍歷的節點數大於k時，前頭變數指向的位置才要跟著向後移動

1
2
3
4
5
6
7
8
9
10
11
var tmp *ListNode
count := 1
front := head
rear := head
for rear != nil && rear.Next != nil {
	if count > k {
		front = front.Next
	}
	rear = rear.Next
	count++
}

但如果後頭的變數位置已經指向了LinkedList的最後一個節點，然而k的值根本就超過整個LinkedList長度的話，此時就直接將k與count取餘數，如果餘數的結果為0表示最後旋轉完所有的節點還停留在相同的位置，便直接將原本的LinkedList原封不動的做回傳，而如果餘數不為0，因為後頭的變數位置已經指向了最後一個節點，前頭的變數位置還停在開頭位置，這時就要直接移動前頭的變數位置到與後頭的位置差k為止，移動次數則為LinkedList長度(count)-k-1

1
2
3
4
5
6
7
8
9
if k >= count {
	k %= count
	if k == 0 {
		return head
	}
	for i := 1; i <= count-k-1; i++ {
		front = front.Next
	}
}

最後的嫁接如果後頭變數位置本身不為空，便將後頭變數位置的下一個嫁接到開頭，接著前頭變數的位置是在原本倒數第k+1個上，而因為後頭的k個都已經移動到開頭了，所以在暫存了倒數第k個的位置後(會變到LinkedList的第一個節點)，就將原本前頭變數位置的下一個改為nil，才回傳先前暫存的位置也就是新的LinkedList第一個節點位置

1
2
3
4
5
6
if rear != nil {
	rear.Next = head
	tmp = front.Next
	front.Next = nil
}
return tmp

完整程式碼:

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
func rotateRight(head *ListNode, k int) *ListNode {
	var tmp *ListNode
	count := 1
	front := head
	rear := head
	for rear != nil && rear.Next != nil {
		if count > k {
			front = front.Next
		}
		rear = rear.Next
		count++
	}
	if k >= count {
		k %= count
		if k == 0 {
			return head
		}
		for i := 1; i <= count-k-1; i++ {
			front = front.Next
		}
	}
	if rear != nil {
		rear.Next = head
		tmp = front.Next
		front.Next = nil
	}
	return tmp
}

總結:

要將LinkedList的節點分別向右移k格(旋轉)，使得最後一個節點的位置紛紛跳躍至開頭，要回傳旋轉後的LinkedList，仔細觀查會發現右移k格時倒數k個節點會移動到開頭，因此只要知道倒數第k+1個節點的位置(與最後一個節點位置差k)，便能直接將後頭整串至底移動到開頭做嫁接，所以一開始就用兩變數指向頭的位置，先移動一指向變數遍歷LinkedList，待兩變數距離超過k時另一個指向變數才跟著向後遍歷，如此一來待後頭的指向變數到底時，前頭指向變數指到的位置就會是倒數第k+1個節點的位置，嫁接完就是我們要的結果了。

分享到