Partition List leetcode

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

解题思路： 创建两个List, left and right

遍历整个list 当小于x放在left 大于放在right

最后让left最后一个元素指向right第一个 

right最后一个指向null

返回 left第一个元素

两个dummynode来确保找到left第一个元素和right第一个元素,
两个指针来对应相应的list left和list right
时间复杂度O(n) 空间O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null || head.next == null){
            return head;
        }
        
        ListNode dummyleft = new ListNode(0);
        ListNode dummyright = new ListNode(0);
        ListNode left = dummyleft;
        ListNode right = dummyright;
        while (head != null ){
            if (head.val < x){
                left.next = head;
                left = left.next;
            } else {
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        left.next = dummyright.next;
        right.next = null;
        return dummyleft.next;
    }
}