The questions briefly

Leetcode 86. Separated linked lists

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.

The sample

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

  1. Check whether head is empty or has only one node.
  2. Create samLL and large linked lists
  3. Compare the value of each node with the size of x;
  • If nodeval < x, samll -> node;
  • Otherwise large -> node;
  1. Samll list tail node points to large list head node (-> NULL)

Javascript 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 == null || head.next == null) return head;
    let small = new ListNode(0), large = new ListNode(0);
    let smHead = small, lgHead = large;
    while(head) {
        if(head.val < x) {
            small.next = head;
            small = small.next;
        }else {
            large.next = head;
            large = large.next;
        }
        head = head.next;
    }
    large.next = null;
    small.next = lgHead.next;
    return smHead.next;
};
Copy the code

Video: bili