Leetcode(86) Partition List

发表于 | 分类于

Description

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

解法

这道题可以将所有小于给定值的节点取出组成一个新的链表，并在原表中删除，此时原链表中剩余的节点的值都大于或等于给定值，只要将原链表直接接在新链表后即可。

对于输入 1 -> 4 -> 3 -> 2 -> 5 -> 2 ，3

此种解法链表变化顺序为：

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2

New:

Original: 4 -> 3 -> 2 -> 5 -> 2

New:　 1

Original: 4 -> 3 -> 5 -> 2

New:　 1 -> 2

Original: 4 -> 3 -> 5

New:　 1 -> 2 -> 2

Original:

New:　 1 -> 2 -> 2 -> 4 -> 3 -> 5

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode res = new ListNode(-1);
        ListNode restmp = res;
        ListNode tmp = head;
        ListNode pre = head;
        while (tmp != null) {
            if (tmp.val < x) {
                ListNode newnode = new ListNode(tmp.val);
                restmp.next = newnode;
                restmp = restmp.next;
                if (tmp == head) {
                    head = tmp.next;
                    pre = head;
                    tmp = head;
                } else {
                    pre.next = tmp.next;
                    tmp = tmp.next;
                }
            } else {
                pre = tmp;
                tmp = tmp.next;
            }
        }
        restmp.next = head;
        return res.next;
    }
}