86. Partition List

Difficulty:
Related Topics:
Similar Questions:

    Problem

    Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

    You should preserve the original relative order of the nodes in each of the two partitions.

    Example:

    Input: head = 1->4->3->2->5->2, x = 3
    Output: 1->2->2->4->3->5
    

    Solution

    /**
     * Definition for singly-linked list.
     * function ListNode(val) {
     *     this.val = val;
     *     this.next = null;
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} x
     * @return {ListNode}
     */
    var partition = function(head, x) {
      var l1 = new ListNode(0);
      var l2 = new ListNode(0);
      var now1 = l1;
      var now2 = l2;
      var now = head;
    
      while (now) {
        if (now.val < x) {
          now1.next = now;
          now1 = now1.next;
        } else {
          now2.next = now;
          now2 = now2.next;
        }
        now = now.next;
      }
    
      now1.next = l2.next;
      now2.next = null;
    
      return l1.next;
    };
    

    Explain:

    nope.

    Complexity: