LeetCode题解-86.分隔链表

发表于 更新于 分类于

题目描述

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

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

示例1:

输入: head = 1->4->3->2->5->2, x = 3

输出: 1->2->2->4->3->5

解题思路

新建两个链表，然后遍历原链表，分别把小于x的节点以及大于等于x的节点加入到新链表，然后再把两个新链表连起来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode small = new ListNode(-1);
        ListNode newHead = small;
        ListNode large = new ListNode(-1);
        ListNode largeHead = large;
        while (head != null) {
            // 比x小的节点放到small链表
            if (head.val < x) {
                small.next = new ListNode(head.val);
                small = small.next;
            } else {
                // 比x大的节点放到large链表
                large.next = new ListNode(head.val);
                large = large.next;
            }
            head = head.next;
        }
        // 连接small和large两个链表
        small.next = largeHead.next;
        return newHead.next;
    }