LeetCode 0086. Separate linked list

【LetMeFly】86. Separate the list

Force button topic link ：https://leetcode.cn/problems/partition-list/

Give you a list of the head node head And a specific value x , Please separate the linked list , Make all Less than x All of the nodes appear in Greater than or equal to x Before the node .

You should Retain The initial relative position of each node in the two partitions .

 

Example 1：

 Input ：head = [1,4,3,2,5,2], x = 3
 Output ：[1,2,2,4,3,5]

Example 2：

 Input ：head = [2,1], x = 2
 Output ：[1,2]

 

Tips ：

• The number of nodes in the linked list is in the range [0, 200] Inside
• -100 <= Node.val <= 100
• -200 <= x <= 200

Method 1 ： Double pointer

We only need to base the original linked list on “ Is less than x” The rules of are divided into two linked lists , Then merge the two linked lists .

First define two new header nodes , Traverse the original linked list , Add each node to the new corresponding linked list .

Last , hold “ Less than x The linked list of ” Of the last node next Point to “ Greater than or equal to x The linked list of ” The first node of , hold “ Greater than or equal to x The linked list of ” Of the last node next empty , return “ Less than x The linked list of ” The first node of the .

See code Notes for detailed implementation .

• Time complexity $O(N)$, among $N$ Is the number of nodes in the original linked list
• Spatial complexity $O(1)$, Only constant nodes are required （ To add a node to the end of the linked list, you only need to modify next The pointer , No extra space is required ）

AC Code

C++

class Solution {
    
public:
    ListNode* partition(ListNode* head, int x) {
    
        ListNode* le = new ListNode, *ge = new ListNode;  //  Less than x The linked list of 、 Greater than or equal to x The linked list of 
        ListNode* p1 = le, *p2 = ge;  //  Two pointers 
        while (head) {
      //  Traverse the original linked list 
            if (head->val < x) {
    
                p1->next = head;  //  Add to “ Less than x The linked list of ” Back 
                p1 = p1->next;  //  Pointer backward 
            }
            else {
    
                p2->next = head;  // //  Add to “ Greater than or equal to x The linked list of ” Back 
                p2 = p2->next;
            }
            head = head->next;
        }
        p1->next = ge->next;  // “ Less than x The linked list of ” The last node of points to “ Greater than or equal to x The linked list of ” The first node of （ The header node is empty , No value stored , So point to ge->next）
        p2->next = nullptr;  // “ Greater than or equal to x The linked list of ” Of the last node next empty 
        return le->next;  //  return “ Less than x The linked list of ” The first node of 
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125467594