Topic describes

Given a list of head nodes and a specific value x, separate the list so that all nodes less than x appear before nodes greater than or equal to x.

You should preserve 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

Tip:

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

Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

• Overall: Create a new list, iterate over the old list, insert items greater than or equal to x behind the new list, and place items less than x in front of the new list.
• Details: when to put in front of the need to follow the principle of first inserted in the front, so forward insert, need to find a new list of the last less than x nodes and greater than or equal to the critical point of x, then inserted into the middle of the two points, didn’t find the critical point, if found at the end of the list is directly into the new list of the last

code

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ / ideas:
// Create a new list, iterate over the old list, insert items greater than or equal to x behind the new list, and place items less than x in front of the new list
/ / details: when to put in front of the need to follow the principle of first inserted in the front, so forward insert, need to find a new list of the last less than x nodes and greater than or equal to the critical point of x, then inserted into the middle of the two points, didn't find the critical point, if found at the end of the list is directly into the new list of the last
/ * * *@param {ListNode} head
 * @param {number} x
 * @return {ListNode}* /
var partition = function(head, x) {
    let nowHead=head;

    let newHead=new ListNode(-201);// Create a header node that must be smaller than x
    while(nowHead){
         let newNode=new ListNode(nowHead.val);// Create a virtual node in the header,
         let current;
       if(newHead&&nowHead.val<x){
             // If val is less than or equal to 3, add all nodes to the end of the list before adding all nodes with val greater than or equal to 3
             current=newHead;
             let parent=current;
             while (current.val<x&&current.next){// If x is greater than or equal to x, the end of the linked list is an insert position
                 parent=current;
                 current=current.next;
             }
             if(current.val>=x){// If you find an item greater than or equal to x, insert the item before it
               newNode.next=parent.next;
               parent.next=newNode;
             }else{If no item greater than or equal to x is found, insert the item to the end of the new list
               letchild=current.next; newNode.next=child; current.next=newNode; }}else{
         // Add other cases to the new list (including first node case and >=x case)
                current=newHead;
                while(current.next){
                    current=current.next;
                }
                 current.next=newNode; 
        }
        nowHead=nowHead.next;
    } 
    return newHead.next;

};
Copy the code