未分類

Partition List

Go, LeetCode, LinkedList, TwoPointers

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example:

1
2
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
提示 解題應用
LinkedList Pointer
TwoPointers Two LinkedList

Default:

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

解答思路:

如果能搞懂題目意思，那麼只需要幾秒的時間就可以想出解法了，最主要就是要將LinkedList分類，如果值比x小就將該節點分一類，如果比x大或相等就分另一類，重點是當節點被歸納至某一類時並不需要做排序，因為只是要相對位置而已，所以被分配到該類時只要接在後頭即可，最後就只要將相對較小的那串LinkedList與相對較較大的另一串LinkedList相接就搞定了。

程式碼解說:

要將LinkedList分配為相對較小的一類與相對較大(或相同)的一類就需要兩個新的LinkedList來分別儲存，所以這邊就初始化一個small與一個big的頭節點來分別儲存(頭節點也能確保之後第一個新加入節點與其它節點一樣有操作上的一致性)，並分別用header來暫存之後兩個LinkedList的第一個節點位置(也就是先前剛新增的頭節點)，接下來就是開始遍歷原本題目給的LinkedList，如果節點的值比目標值小就將該節點接到small那串LinkedList的後頭，反之如果值比較大或相等則接到big那串LinkedList的後頭，待遍歷結束後，最後只要將兩個分配好的LinkedList嫁接(small的下一個節點位置接到big頭節點的下一個位置)，接著再將big的下一個位置改為nil就可以回傳新重組完LinkList的位置了(也就是small頭節點的下一個位置)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
small := &ListNode{}
smallHeader := small
big := &ListNode{}
bigHeader := big
for head != nil {
	if head.Val < x {
		small.Next = head
		small = head
	} else {
		big.Next = head
		big = head
	}
	head = head.Next
}
small.Next = bigHeader.Next
big.Next = nil
return smallHeader.Next

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func partition(head *ListNode, x int) *ListNode {
	small := &ListNode{}
	smallHeader := small
	big := &ListNode{}
	bigHeader := big
	for head != nil {
		if head.Val < x {
			small.Next = head
			small = head
		} else {
			big.Next = head
			big = head
		}
		head = head.Next
	}
	small.Next = bigHeader.Next
	big.Next = nil
	return smallHeader.Next
}

總結:

若LinkedList需要依某個特定的值來分類，並依該值將LinkedList重新組合(比該值小的就依相對位置放置前頭;比該值大或相等就依相對位置放置後頭)，其做法是如果值比該值小就將該節點分一類(放置於新的LinkedList)，如果比該值大或相等就分另一類，被分配到該類時直接在後頭即可，最後就只要將相對較小的那串LinkedList與相對較較大的另一串LinkedList相接就搞定了。

分享到