[LeetCode] 86. Partition List

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.

Thought process:

The idea is to use two dummy nodes and two pointers. leftDummy.next is the sub-list where each node is less than x, and rightDummy.next is the sub-list where each node is greater than or equal to x. Link two lists together to get the partitioned list.

Solution:

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

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

Time complexity: O(n).