給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前。

你應當保留兩個分區(qū)中每個節(jié)點的初始相對位置。

示例:

輸入: head = 1->4->3->2->5->2, x = 3

輸出: 1->2->2->4->3->5

題目分析：本題讓我們把原來的鏈表進行分隔，小于x的在前，大于等于x的在后。并且，元素之間還需要保持原有的相對順序。在下面的圖例中，我們可以看到原有元素的順序。分隔完后，在原來索引位置5處的元素2依然排在索引位置為3處的元素2之后。

在思考這道題如何解的時候，我們先回憶一下我們在算法課中也接觸過類似的partition方法，這種方法在quick sort（快速排序）中也出現(xiàn)過。快速排序采用分治的思想，通過某一分界值將數(shù)組分成左右兩部分，將大于等于分界值的數(shù)據(jù)集中到右側(cè)，將小于分界值的數(shù)據(jù)集中到左側(cè)。然后分別對左側(cè)右側(cè)進行上述處理，直到每一側(cè)都排好序，那么整體也就排好序了。我們看下面的這個例子，對原數(shù)組我們選擇最后一個元素作為分界值，然后左側(cè)都是小于70的元素，右側(cè)都是大于70的元素。然后對于左側(cè)和右側(cè)，我們選擇他們中的最后一個元素作為分界值繼續(xù)進行劃分，一直到最后每一側(cè)都排好序（即這一側(cè)只含有一個元素或者為空），該算法停止。該算法的時間復雜度為O(nlogn)。

對應的C++參考代碼如下

int partition(vector<int> &input, int low, int high) { int pivot = input[high]; int i = low - 1; for (int j = low; j <= high - 1; j++) { if (input[j] < pivot) { ++i; swap(input[i], input[j]); } } swap(input[i + 1], input[high]); return i + 1; } void quickSort(vector<int> &input, int low, int high) { if (low < high) { int index = partition(input, low, high); quickSort(input, 0, index - 1); quickSort(input, index + 1, high); } }

回到本題中，既然需要將鏈表分隔為兩部分，那么我們可以設置兩個dummy節(jié)點分別保存鏈表的一部分，dummy1作為小于x的節(jié)點的鏈表的頭結(jié)點，dummy2作為大于等于x的節(jié)點的鏈表的頭結(jié)點，如果當前節(jié)點的值小于x，我們就將當前節(jié)點放到dummy1鏈表的末尾。如果當前節(jié)點的值大于等于x，我們就將其插入dummy2鏈表的末尾。這樣我們就將原鏈表劃分成了兩部分，并且保證了相對順序。最后鏈接成的鏈表結(jié)果如下圖顯示，我們的算法時間復雜度為O(n)。下面分別給出不同語言的代碼實現(xiàn)。

C++代碼

ListNode* partition(ListNode* head, int x) { if (head == NULL || head->next == NULL) return head; ListNode* dummy1 = new ListNode(0); ListNode* dummy2 = new ListNode(1); ListNode *tail1 = dummy1, *tail2 = dummy2; ListNode* curr = head; while (curr != NULL) { if (curr->val < x) { tail1->next = curr; tail1 = tail1->next; } else { tail2->next = curr; tail2 = tail2->next; } curr = curr->next; } if (tail1 == NULL) return tail2; if (tail2 == NULL) return tail1; tail2->next = NULL; tail1->next = dummy2->next; return dummy1->next; }

Java代碼

public ListNode partition(ListNode head, int x) { if (head == null || head.next == null) return head; ListNode dummy1 = new ListNode(0); ListNode dummy2 = new ListNode(0); ListNode smallTail = dummy1, largeTail = dummy2; ListNode curr = head; while (curr != null) { if (curr.val < x) { smallTail.next = curr; smallTail = smallTail.next; } else { largeTail.next = curr; largeTail = largeTail.next; } curr = curr.next; } smallTail.next = dummy2.next; largeTail.next = null; return dummy1.next; }

C#代碼

public ListNode Partition(ListNode head, int x) { if (head == null || head.next == null) { return head; } ListNode dummy1 = new ListNode(0); ListNode dummy2 = new ListNode(0); ListNode smallTail = dummy1, largeTail = dummy2; ListNode curr = head; while (curr != null) { if (curr.val < x) { smallTail.next = curr; smallTail = smallTail.next; } else { largeTail.next = curr; largeTail = largeTail.next; } curr = curr.next; } smallTail.next = dummy2.next; largeTail.next = null; return dummy1.next; }

Golang代碼

func partition(head *ListNode, x int) *ListNode { if head == nil || head.Next == nil { return head } dummy1 := new(ListNode) dummy2 := new(ListNode) smallTail := dummy1 largeTail := dummy2 curr := head for curr != nil { if curr.Val < x { smallTail.Next = curr smallTail = smallTail.Next } else { largeTail.Next = curr largeTail = largeTail.Next } curr = curr.Next } smallTail.Next = dummy2.Next largeTail.Next = nil return dummy1.Next }

Python3代碼

def partition(self, head: ListNode, x: int) -> ListNode: if head == None or head.next == None: return head dummy1 = ListNode(0) dummy2 = ListNode(0) smallTail = dummy1 largeTail = dummy2 curr = head while curr != None: if curr.val < x: smallTail.next = curr smallTail = smallTail.next else: largeTail.next = curr largeTail = largeTail.next curr = curr.next smallTail.next = dummy2.next largeTail.next = None return dummy1.next

由本題可見，一些經(jīng)典的算法我們還是要學透吃透，這樣在碰到類似問題或者問題變種的時候才能將經(jīng)典算法應用過來，快速解決問題。

總結(jié)

以上是生活随笔為你收集整理的Leetcode 86. 分隔链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。