长大后想做什么？做回小孩！

0%

LeetCode——分隔链表

发表于 分类于 Valine：
本文字数： 130

NO.86 分隔链表 中等

GQke8U.png

思路一：尾插法创建链表 创建两个链表，min存放小于x的节点，max存放大于等于x的节点，遍历参数链表采用尾插法创建这两个链表。最后将max连接到min后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode partition(ListNode head, int x) {
    if (head==null||head.next==null)return head;
    //创建两个链表
    ListNode min=new ListNode(-1),max=new ListNode(-1);
    ListNode minP=min,maxP=max;
    //遍历参数链表
    while (head != null) {
        if (head.val < x) {
            minP.next=head;
            minP=head;
        }else {
            maxP.next=head;
            maxP=head;
        }
        head=head.next;
    }
    //连接min和max，注意排除掉两个链表的哑节点
    minP.next=max.next;
    maxP.next=null;
    return min.next;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github