Look a hundred times beauty, beauty is not necessarily yours. But if you run the algorithm a hundred times, the knowledge is yours

Who can have nine floors? No need to get up!

Title address

The title

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]Copy the code

Example 2:

Input: head = [2,1], x = 2Copy the code

Tip:

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

Their thinking

  • Divide the linked list into two linked lists, which are less thanxIs greater than or equal toxThe big list
  • Join the small linked list with the large linked list to complete the problem

The problem solving code

var partition = function(head, x) {
    if(! head||! head.next)return head
    let vnodeBig = new ListNode(-1,head)
    let vnodeSmall = new ListNode(-1,head)
    let big = vnodeBig
    let small = vnodeSmall
    while(head){
        if(head.val<x){
            small.next = head
            small = small.next
        }else{
            big.next =head
            big = big.next
        }
        head = head.next
    }
    big.next = null
    small.next = vnodeBig.next
    return vnodeSmall.next
};
Copy the code

If you have any questions or suggestions, please leave a comment!