LC.86. Partition List

https://leetcode.com/problems/partition-list/description/

Given a linked list and a target value T, partition it such that all nodes less than T are listed before the nodes larger than or equal to target value T. The original relative order of the nodes in each of the two partitions should be preserved.

Examples

L = 2 -> 4 -> 3 -> 5 -> 1 -> null, T = 3, is partitioned to 2 -> 1 -> 4 -> 3 -> 5 -> null

 1 public ListNode partition(ListNode head, int target) {
 2     // Write your solution here
 3     if(head == null || head.next == null) return head ; 
 4     ListNode smallHead = new ListNode(0),
 5                      smallCurr =  smallHead,
 6              largeHead = new ListNode(0), 
 7                      largeCurr = largeHead, 
 8                      curr = head ; 
 9     //no need to keep head
10     while(curr != null){
11             if(curr.value<target){
12             smallCurr.next = curr ; 
13           smallCurr = smallCurr.next ; 
14         } else{
15             largeCurr.next = curr ; 
16           largeCurr = largeCurr.next ; 
17         }
18           curr = curr.next; 
19     }
20     //this is super important! otherwise circle!
21     largeCurr.next = null ; 
22     //用dummy 的好处，不用担心 small 里到底有没有值
23     smallCurr.next = largeHead.next ; 
24     return smallHead.next ; 
25   }