1. Title Description

  • 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

Analysis of the

  • First, based on the reference value of the linked listx, split the linked list into two, greater than or equal toxThe point tobig That is less thanx The point tosmall.curThe linked list of pointing operations

  • Greater than or equal toxThe node ofbigAfter the pointer, less than or equal toxOn thesmallPointer behind and movecurThe list

  • mobilecurGo back n steps until the linked list is zeroNull, our linked list is split into two linked lists

Two, code implementation

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} x * @return {ListNode} */ var partition = function(head, x) { if(! head) return null; let big = new ListNode() , small = new ListNode(); let bigNode = big , smallNode = small; for(let cur = head, next; cur; cur = next){ next = cur.next; cur.next = null; if(cur.val < x){ smallNode.next = cur; smallNode = cur; }else{ bigNode.next = cur; bigNode = cur; } } smallNode.next = big.next; return small.next; };Copy the code

This completes the pin-pin-swap list. Welcome to the triplet