【小白爬Leetcode86】1.6分隔链表 Partition List

Leetcode 86 $\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;
    }
};

结果如下：