從LeetCode學演算法 - 82 Linked List (10)

0086. Partition List (Medium)

寫在前面

再過兩天就是投票日了，懇請各位讀者們，
不論支持誰，都要好好地去了解候選人們及政黨的政見，
在1/11投下您寶貴的一票。**

筆者在這裡提醒大家去思考一下：
程式的世界很單純，很多東西不是True就是False，
而一個按照正常邏輯運行的程式，最終該呈現怎樣的結果，
大抵都是可以預期的。

想像一下，如果一個同事常常遲到早退，罔顧專案進度，
讓大家必須要幫忙收拾爛攤子；
話說的很滿，遇到事情卻推拖閃躲，
顧左右而言他的話，相信這樣的人，
我們不會希望其成為自己的頂頭上司。

既然如此，我們會希望這種人成為自己的大老闆嗎？

運用簡單的邏輯思考，相信聰明的各位都能得到正確答案。
儘管這種人的餅畫得再大再漂亮，我們知道，
那都不是真的，因為我們難以相信一個沒有誠信的人能夠說到做到。

Question

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.

Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

分析/解題

給定一個Linked List和一個值x，使用x來將所有節點進行分段，
令較x小的節點排在≥x的分段位置的前面。
注意在分段時，同時也要保有原先兩段的節點順序。

這題其實有點像是之前我們在講Merge Two Sorted Lists的感覺，
為了要能夠讓兩個段落分開且照順序，
我們應該要有兩個做為頭的dummy節點 ，稱為d1/d2。
所有小於x的部分都接到d1，反之則接到d2。
那麼實際上來說，我們只要將整個List遍歷過一遍，
就可以依照實際和x之間的比較，來決定要將這次看到的節點 ，
必須要接到d1還是d2上面。

由於最後我們需要將兩段接起來，
所以d1/d2保持不動的狀況下，
我們需要另一個變數來儲存現在遍歷的部份走到的節點，
先稱其為ite1/ite2，所以ite1/ite2起始分別是d1/d2。

那麼，按照邏輯來說，我們可以能會想到下面的寫法：

1
2
3
4
if (head.val < x) {
 　ite1.next = head;
 　ite1 = ite1.next;
}

但這麼考慮欠缺了一個條件：
當我們選定ite1.next = head時，head裡面還藏有它的next的資訊 ，
造成你以為是只有納入head，殊不知head.next也被隱含進去了 ！
要解決這個問題，我們可以將ite1.next重新設為null 。
問題來了，這一設為null，反而變成head的資訊就消失了 ，
同時head.next的資訊也消失了 。

所以，我們要一開始用一個nxt的ListNode來記錄head.next，
接下來兩種狀況下的next相關操作做完以後，
最後再讓head接上先前儲存的nxt。

依此，寫成程式碼。

Java

Java的部分，我們先用直觀的方式來處理，
所以包含前面的處理都完整的話，
我們應該能得到d1及其後面的一組(直到ite1)、
d2及其後面的另一組(直到ite2)，
若其中一個沒有接上任何節點的話，
可以直接吐出d1.next/d2.next 的狀況。
若兩者皆有，則先將第一排的結尾接給第二排的開頭 ，
最後回傳d1.next即可。

同時，運用陣列可以更輕鬆地化簡邏輯，
這裡將改善過後的版本放在註解欄中。

Python

就Python的部分而言，只要使用跟前述相近的處理方式，
最後再回傳d1.next 即可。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VEQZV7E**