分隔链表

发表于
本文字数： 917 阅读时长 ≈ 1 分钟

LeetCode每日一题，86. Partiton List

先看题目描述

s9QtA0.png

大意就是给定一个链表和一个整数 x，让我们将链表分隔，使 小于 x 的节点在大于等于 x 的节点之前，且要求不能改变链表中节点的相对顺序，让我们返回分隔后的链表

算法和思路

只需维护 l1 和 l2 两个链表，其中 l1 按顺序存储小于 x 的节点，l2 按顺序存储大于等于 x 的节点，最后将 l1 和 l2 两个链表连接即可，最后连接时记得要将 l2 的末尾节点的 next 指针置空

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dump1 = new ListNode(0);
        ListNode dump2 = new ListNode(0);
        ListNode cur1 = dump1;
        ListNode cur2 = dump2;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            if (cur.val < x) {
                cur1.next = cur;
                cur1 = cur1.next;
            } else {
                cur2.next = cur;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        cur2.next = null;
        cur1.next = dump2.next;
        return dump1.next;
    }
}