As a perennial front er, it’s time to let yourself practice some basic algorithms. Today is the first day, um… Don’t say a word, just turn it on!

You are given a list of head nodes and a specific value x. Please 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.

Input: head = [1,4,3,2,5,2], x = 3 output: [1,2,2,4,3,5]Copy the code

Divide a linked list into two halves, and then connect them. Define two empty lists, the one larger than the given value is put together, the one smaller than the given value is put together, and then the small value list points to the large value list

[Code] :

/** * 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 || head.val ===null) return null

    let left = new ListNode(),right = new ListNode(),l = left,r = right

    while(head! =null) {if(head.val < x) {
            left.next = head
            left= left.next
        }else{
            right.next = head
            right = right.next
        }
        head = head.next
    }
    left.next = r.next
    right.next = null
    r.next = null
    return l.next
};
Copy the code

The js brush algorithm is a bit of an oddball when it comes to linked lists. The code can run directly on a link, but if you want to test it in a local Node environment, you need to do a few extra things:

// Array list
function arrayList(ary) {
  if(! ary.length) {return null
  }

  var node
  var head = {val: ary[0].next: null}
  var pnode = head  // The pnode variable is used to hold the previous node

  for(var i = 1; i < ary.length; i++) {
      node = {val: ary[i], next:null}
      pnode.next = node   // Next of the previous node points to the current node
      pnode = node   // Assign node to pNode
  }

  return head
}

// List to array
function listArray(head) {
  if(! head) {return[]}var result = [head.val]
  var restValues = listArray(head.next)
  return result.concat(restValues)
}
Copy the code

Try it on:

const example = [0.8.1.3.4.5.7.2.4.3.2.5.2]
test(`${example}= > `.() = > {
  expect(listArray(partition(arrayList([0.8.1.3.4.5.7.2.4.3.2.5.2]), 3))).toStrictEqual([0.1.2.2.2.8.3.4.5.7.4.3.5])})Copy the code

Done! Sleep!