未分類

Reverse Linked List II

Go, LeetCode, LinkedList

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:

1
2
3
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

Note:

Given m, n satisfy the following condition:

1 ≤ m ≤ n ≤ length of list.

提示 解題應用
LinkedList Pointer

Default:

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

解答思路:

很早之前曾寫過Reverse Linked List，當初只是要將整個LinkedList做翻轉，所以難度不會太高，這次雖然與先前一樣可以只遍歷一遍就完成部分區塊的翻轉，但要考慮的事情就會稍為多一點，好比說整個LinkedList翻轉最後只要將原本最後一個節點的位置做回傳即可(因為翻轉後會變到第一個)，可是部分區塊的翻轉就不一定了，有可能還是原本是節點位置或是LinkedList上的任一點，端看要翻轉的區塊落在哪裡，所以就需要再自行新增一個頭節點，用以回傳在該節點後頭翻轉完新LinkedList的第一個節點位置，最後就是部分區塊的翻轉還要稍為思考要如何與未翻轉的區塊做連結，大致流程如下:

原本的LinkedList:

1
1 → 3 → 5 → 7 → 9

部分區塊翻轉後的LinkedList(2~4):

1
1 → 3 ← 5 ← 7 → 9

最後翻轉後的區塊與未翻轉的區塊做連結:

1
2
3
   ┌ – – – – – ↓
1  3 ← 5 ← 7  9
∟ – – – – – ↑

程式碼解說:

因為這次要做的是區塊的翻轉，所以除了要自行新增一個頭節點以回傳後頭新LinkedList的第一個節點位置之外，翻轉後的區塊要與未翻轉的區塊做連結時，要多紀錄翻轉區塊m~n的前一個節點的位置(m-1)與在該區塊中翻轉後最後一個節點的位置(也就是該區塊翻轉前第一個節點的位置:m)以利後續做嫁接連結，這邊以preFront與rear分別表示，隨後就是正式開始遍歷原始的LinkedList並一邊計算節點數，用以知曉是否已到達要翻轉的範圍之中，如果遍歷的節點數尚未到達m就繼續向下遍歷(到達m-1與m就先紀錄當下的位置到preFront與rear)，直到範圍落在m~n之中才開始翻轉節點(翻轉細節解說可以參考之前的文章)，最後如果知道下一個節點會超過m~n之間的範圍並且不再需要再翻轉的話，此時就可以將翻轉後的區塊與未翻轉的區塊做嫁接，也就是m-1的位置(preFront)接到n的位置，m的位置(rear)接到n+1的位置，連結完後便可以結束遍歷，直接回傳先前自製頭節點的下一個位置

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
var flag *ListNode
var rear *ListNode
var preNode *ListNode
count := 1
header := &ListNode{0, head}
preFront := header
for head != nil {
	if count < m {
		preFront = head
	} else if count == m {
		rear = head
	}
	flag = head
	head = head.Next
	if count >= m && count <= n {
		flag.Next = preNode
	}
	preNode = flag
	if count+1 > n {
		preFront.Next = flag
		rear.Next = head
		break
	}
	count++
}
return header.Next

完整程式碼:

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 reverseBetween(head *ListNode, m int, n int) *ListNode {
	var flag *ListNode
	var rear *ListNode
	var preNode *ListNode
	count := 1
	header := &ListNode{0, head}
	preFront := header
	for head != nil {
		if count < m {
			preFront = head
		} else if count == m {
			rear = head
		}
		flag = head
		head = head.Next
		if count >= m && count <= n {
			flag.Next = preNode
		}
		preNode = flag
		if count+1 > n {
			preFront.Next = flag
			rear.Next = head
			break
		}
		count++
	}
	return header.Next
}

總結:

可以先參考之前寫的Reverse Linked List，翻轉的做法一樣，只是先前是翻轉整個LinkedList，現在則是再給予範圍要將區塊內的節點全數做翻轉，相較先前翻轉整個LinkedList來說，原本只要將最後一個節點的位置做回傳即可(因為翻轉後會變到第一個)，可是部分區塊的翻轉就不一定了，有可能還是原本是節點位置或是LinkedList上的任一點，端看要翻轉的範圍落在哪裡，所以就需要再自行新增一個頭節點，用以回傳在該節點後頭翻轉完新LinkedList的第一個節點位置，最後就是部分區塊的翻轉後要如何與未翻轉的區塊做連結才是一大重點。

分享到