86.分隔链表.md

86. 分隔链表

url

题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
输入：head = [2,1], x = 2
输出：[1,2]

方法

code

js

let partition = (head, x) => {
    let dummy1, dummy2 = new ListNode(0);
    let node1 = dummy1, node2 = dummy2;
    while (head !== null) {
        if (head.val < x) {
            node1.next = head;
            head = head.next;
            node1 = node1.next;
            node1.next = null;
        } else {
            node2.next = head;
            head = head.next;
            node2 = node2.next;
            node2.next = null;
        }
    }
    node1.nex = dummy2.next;
    return dummy1.next;
}

go

func partition(head *ListNode, x int) *ListNode {
    if head == nil {return nil}
    dummy1, dummy2 := &ListNode{}, &ListNode{}
    cur1, cur2 := dummy1, dummy2
    for head != nil {
        if head.Val < x {
            cur1.Next = head
            head = head.Next
            cur1 = cur1.Next
            cur1.Next = nil
        } else {
            cur2.Next = head
            head = head.Next
            cur2 = cur2.Next
            cur2.Next = nil
        }
    }
    cur1.Next = dummy2.Next
    return dummy1.Next
}

java

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(0);
        ListNode dummy2 = new ListNode(0);
        ListNode node1 = dummy1, node2 = dummy2;
        while (head != null) {
            if (head.val < x){
                node1.next = head;
                head = head.next;
                node1 = node1.next;
                node1.next = null;
            } else {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            }
        }
        node1.next = dummy2.next;
        return dummy1.next;
    }
}