Partition List

Given a linked list and a valuex, partition it such that all nodes less thanxcome before nodes greater than or equal tox.

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

For example,
Given1->4->3->2->5->2andx= 3,
return1->2->2->4->3->5.

分析

需要对头进行add/remove 就要用fakeHead (dummyHead)

图解

代码

class Solution {
    public ListNode partition(ListNode head, int x) {
        //需要对头进行add就要用fakeHead
        ListNode left_dummy = new ListNode(-1);
        ListNode right_dummy = new ListNode(-1);

        ListNode left_cur = left_dummy;
        ListNode right_cur = right_dummy;

        for(ListNode cur = head; cur!=null; cur = cur.next){
            if(cur.val<x){
                left_cur.next = cur;
                left_cur=cur;
            }else{
                right_cur.next = cur;
                right_cur=cur;
            }
        }

        left_cur.next = right_dummy.next;
        right_cur.next = null;//思考为何一定需要这步？ 省去这步会出现什么问题？

      return left_dummy.next;  
    }
}