LeetCode题解|86. Partition List

题目链接：86. Partition List

概述

这个题目给定一个单链表L以及一个整数x，使得所有小于x的节点在大于等于x的节点之前，同时要保证顺序和原链表一致。

思路

这个题目只要创建两个链表，遍历一遍原链表L，将所有节点按照要求，分别插入到两个新链表中，就完成了分隔，紧接着在将两段链表连接起来，即可得到答案。

实现

/**
 * 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) {
    if(head == null){
        return null;
    }
    var smaller = p1 = new ListNode(null),
        larger = p2 = new ListNode(null);

    while(head != null){
        if(head.val < x){
            smaller.next = head;
            smaller = smaller.next
        }
        else{
            larger.next = head;
            larger = larger.next;
        }
        head = head.next;
    }
    larger.next = null;
    smaller.next = p2.next;
    
    return p1.next;
};

题解合集