六六力扣刷題連結清單之分隔連結清單

前言

之前小六六一直覺得自己的算法比較菜，算是一個短闆吧，以前刷題也還真是三天打魚，兩台曬網，刷幾天，然後就慢慢的不堅持了，是以這次，借助平台的活動，打算慢慢的開始開刷，并且自己還會給刷的題總結下，談談自己的一些思考，和自己的思路等等，希望對小夥伴能有所幫助吧，也可以借此機會把自己短闆補一補，希望自己能堅持下去呀

連結清單

• ​​六六力扣刷題連結清單之移除連結清單元素​​
• ​​六六力扣刷題連結清單之反轉連結清單​​
• ​​六六力扣刷題連結清單之兩兩交換連結清單中的節點​​
• ​​六六力扣刷題連結清單之合并兩個有序連結清單​​
• ​​六六力扣刷題連結清單之反轉連結清單 II​​

連結清單的理論基礎

連結清單的種類主要為：單連結清單，雙連結清單，循環連結清單

連結清單的存儲方式：連結清單的節點在記憶體中是分散存儲的，通過指針連在一起。

連結清單是如何進行增删改查的。

數組和連結清單在不同場景下的性能分析。

可以說把連結清單基礎的知識都概括了，但又不像教科書那樣的繁瑣。

虛拟頭結點

連結清單的一大問題就是操作目前節點必須要找前一個節點才能操作。這就造成了，頭結點的尴尬，因為頭結點沒有前一個節點了。

每次對應頭結點的情況都要單獨處理，是以使用虛拟頭結點的技巧，就可以解決這個問題。

題目

給你一個連結清單的頭節點 head 和一個特定值 x ，請你對連結清單進行分隔，使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前。

你應當 保留 兩個分區中每個節點的初始相對位置。

輸入： head = [1,4,3,2,5,2], x = 3
輸出：[1,2,2,4,3,5]      

輸入： head = [1,4,3,2,5,2], x = 3
輸出：[1,2,2,4,3,5]      

思路

直覺來說我們隻需維護兩個連結清單 small 和 large 即可，\textit{small}small 連結清單按順序存儲所有小于 xx 的節點，large 連結清單按順序存儲所有大于等于 xx 的節點。周遊完原連結清單後，我們隻要将 small 連結清單尾節點指向large 連結清單的頭節點即能完成對連結清單的分隔。

為了實作上述思路，我們設 smallHead 和 largeHead 分别為兩個連結清單的啞節點，即它們的 next 指針指向連結清單的頭節點，這樣做的目的是為了更友善地處理頭節點為空的邊界條件。同時設 small 和 large 節點指向目前連結清單的末尾節點。。随後，從前往後周遊連結清單，判斷目前連結清單的節點值是否小于 xx，如果小于就将 small 的 next 指針指向該節點，否則将 large 的 next 指針指向該節點。

周遊結束後，我們将 large 的 next 指針置空，這是因為目前節點複用的是原連結清單的節點，而其 next 指針可能指向一個小于 xx 的節點，我們需要切斷這個引用。同時将 small 的 next 指針指向 largeHead 的 next 指針指向的節點，即真正意義上的 large 連結清單的頭節點。最後傳回 smallHead 的 next 指針即為我們要求的答案。

題解

package com.six.finger.leetcode.two;

import com.six.finger.leetcode.common.ListNode1;

public class Partition {


    public ListNode1 partition(ListNode1 head, int x) {

        ListNode1 first = new ListNode1(0);

        ListNode1 firstHead = first;

        ListNode1 last = new ListNode1(0);
        ListNode1 lastHead = last;

        while (head != null) {
            if (head.val >= x) {
                last.next = head;
                last = last.next;
            } else {

                first.next = head;
                first = first.next;
            }
            head = head.next;
        }
        last.next = null;
        first.next = lastHead.next;

        return firstHead.next;      

結束