文章目錄
- 題目
- 解題思維
- 代碼
- 附圖
題目
這個題目中的 “分隔”并不是真正意義上分隔，將一個鏈表分隔成兩個鏈表，
而是說 以一個整形資料x，讓鏈表以 val 和 x 之間的大小差距進行陣列分隔，val值小于x的節點，位于左邊，大于和等于則位于整個鏈表的右邊，
而且還有一個要求： 不能是 “無序的”，按照原有相對位置，
什么意思呢？假設 x == 3 ， 第一個 節點的值 是 1，小于x值，而且本身就位于左邊，我們就不用去移動它的位置了，這就是題目中 的 保留每個節點的初識相對位置，
再換一個說法 ： 看到上面那個圖中的 val 為 2 的節點沒？它 和 val值為1的節點 ，val值都小于 x值（3），位于 鏈表的左邊，但是由于它原先就位于 1 的右邊，那么“分隔”后的結果 這個2節點 應該在 1 節點的后面，
這就是 保留 每個節點的初識相對位置，
?
解題思維
建立 兩個傀儡頭節點 small 和 large，small 用來連接 val 值小于x的節點，large 用來連接 val 值大于或等于的節點，
再為 small 和 large 兩個頭節點創建2個替身變數 smallHead 和 largeHead，讓它們記住small 和 large 的頭節點的位置，讓small 和 large 去 連接/遍歷 各自的鏈表，（嗯，好像對 small 和 large 不厚道，誰讓新建的兩個節點參考帶個 頭head 呢？ 嗯 ，沒錯！是這樣的，）
?
代碼
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode();
ListNode smallHead = small;
ListNode large = new ListNode();
ListNode largeHead = large;
while(head != null){
if(head.val < x){
small.next = head;
small = small.next;
}else{
large.next = head;
large = large.next;
}
head = head.next;
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
}
}
附圖
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/393123.html
標籤：java
下一篇：Java語言中的運算子