leetcode 86 Partition List
z
 2018-05-26 17:23:24  

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
  • 把所有小于x的数放在x的左边，大于等于x的数放在右边。
  • 从左往右依次遍历一遍数组，设置两个标记分别标记左边和右边
  • 把小于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
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode left = new ListNode(0);
        ListNode right = new ListNode(0);
        ListNode small = left;
        ListNode great = right;
        ListNode p = head;
        if(p == null || p.next == null){
            return p;
        }
        while(p != null){
            if(p.val < x){
                small.next = p;
                small = small.next;
            }
            else{
                great.next = p;
                great = great.next;
            }
            p = p.next;
        }
        small.next = right.next;
        great.next = null;
        return left.next;
        
    }
}
  • 注意最后的great.next一定要设置成空。不然对于这种情况：
  • 1->2->3->6->4会形成环