Leetcode–Partition List

The Problem:

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.

Notes:

  1. A basic linked list question, use fake head to avoid the mess of dealing with head.
  2. Mistake I made: While nodes are all rearranged, don’t forget the set the next of tail to null, otherwise will link back to a cycle.

Java Solution:

/**
 * 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) {
        ListNode fkHead = new ListNode(0);
        ListNode pre1 = fkHead;
        ListNode fkHead2 = new ListNode(0);
        ListNode pre2 = fkHead2;
        
        fkHead.next = head;
        ListNode p = head;
        while(p!= null){
            if(p.val < x){
                pre1.next = p;
                pre1 = p;
            }
            else{
                pre2.next = p;
                pre2 = p;
            }
            p = p.next;
        }
        pre1.next = fkHead2.next;
        pre2.next = null; //---!!!---important
        return fkHead.next;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s