【小白爬Leetcode86】1.6分隔連結清單 Partition List

• 題目
• • Description
  • 中文描述
• 思路一 找到需要插入的節點M,再進行插入
• 思路二 巧用臨時頭節點

Leetcode 86 m e d i u m \color{#FF7D00}{medium} medium

點選進入原題連結：LeetCode中國站

題目

Description

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:

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

中文描述

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

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

示例：

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

思路一 找到需要插入的節點M,再進行插入

思路：

0.周遊連結清單，需要用到兩個指針pre（指向上一個節點）和cur(指向目前節點)，基操。】

1.根據題意，周遊連結清單的過程中，遇到的第一個val值大于等于x的 節點M 就是我們要插入的地方。那麼為了能在這個節點前插入後續節點，我們需要兩個指針insert_pre（指向第M-1個節點）和 insert_back （指向第M個節點）；

2.在找到 節點M 之前，遇到val小于x的節點，直接略過（保留節點初始相對位置）；例如：在題目給的案例中，我們略過了第一個節點(val ==1)。繼續周遊，直到找到節點M。這個案例中的 節點M 則是第二個節點(val == 4)。

3.找到 節點M 之後，我的天空，星星都亮了…

，遇到val值小于x的節點，就需要把這個節點插入到節點M之前(也就是insert_back之前)。例如：在題目給的案例中，我們需要将第四個節點(val == 2)和第六個節點 (val == 2) 依次插入到節點M （第二個節點）之前，插入的代碼如下：

if(insert_back)   //如果找到了插入位置
{
    pre->next = cur->next; //挖出
    cur->next = insert_back;  //接到前面
    if(insert_pre){insert_pre->next = cur;insert_pre = cur;} 
    else{head = cur;insert_pre = cur;}   //如果第一次前移的節點變成了頭節點，那麼相應地，head也要改變
}
           

注：插入的時候要考慮兩種情況：

第一種：

節點M 是目前連結清單的第一個節點，這種情況下第一次插入的時候需要注意将head指針改成cur（目前要插入的指針）。注意insert_pre要前移一個(指派成cur)；

第二種：

節點M 是中間節點，這種情況隻需要注意insert_pre每次插入要前移一個(指派成cur)就好。

4.最後return head即可。

完整代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* insert_pre = NULL;
        ListNode* insert_back = NULL;

        while(cur)
        {
            if(cur->val >= x )
            {if(!insert_back){insert_pre = pre;insert_back=cur;}}
            else
            {
                if(insert_back)   //如果找到了插入位置
                {
                    pre->next = cur->next; //挖出
                    cur->next = insert_back;  //接到前面
                    if(insert_pre){insert_pre->next = cur;insert_pre = cur;}
                    else{head = cur;insert_pre = cur;}   //如果第一次前移的節點變成了頭節點，那麼相應地，head也要改變
                }
            }
            pre = cur;
            cur = cur->next;
        }
        return head;
    }
};
           

AC後結果如下：

思路二 巧用臨時頭節點

思路來自 bilibili，原視訊連結

維護兩個連結清單，一個是val值小于x的連結清單，統一連接配接到虛節點less_head後面；一個是val值大于x的連結清單，統一連接配接到虛節點more_head後面。當然這個過程需要借助less_ptr和more_ptr這兩個指針。

周遊結束後，将less_ptr指向more_head的下一個節點即可實作兩個連結清單的重新連接配接。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode less_head(0);
        ListNode more_head(0);
        ListNode* less_ptr = &less_head;
        ListNode* more_ptr = &more_head;
        while(head)
        {
            if(head->val<x)
            {
                less_ptr->next = head;
                less_ptr = head;
            }
            else
            {
                more_ptr->next = head;
                more_ptr = head;
            }
        head = head->next;
        }
        less_ptr -> next = more_head.next;
        more_ptr->next = NULL;
        return less_head.next;
    }
};
           

結果如下：