Separate linked lists (86)

Separated list

Given a linked list and a value x, please place the nodes with a value less than x before those with a value greater than or equal to x.

The problem solving code

Join values greater than or equal to x to one list and values less than x to the other. Finally join two linked lists

var partition = function(head, x) {
  if(! head)return null;
  let rs = new ListNode(); // store < x
  let rb = new ListNode(); // Store at least x
  let r1 = rs; // small chain header pointer
  let r2 = rb; // Large chain header pointer
  let p = head; // The list passed in
  let q;
  while (p) {
    q = p.next; // Store the next node
    if (p.val < x){ // less than x is stored in r1
      p.next = null; // Disconnect the connection
      r1.next = p; 
      r1 = p;  // Make sure r1 is the last node in the list
    } else {
      p.next = null; // Disconnect the connection
      r2.next = p;
      r2 = p; // Make sure r2 is the last node in the list
    }
    p = q; // The original list points to the next digit, and the loop continues
  }
  r1.next = rb.next; R1 is smaller than the tail node, and r1 is larger than the head node
  return rs.next; // Returns a node whose storage is smaller than the list head
};
Copy the code