Tuesday, January 21, 2014

Leetcode: 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.

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 begSmaller = new ListNode(0);
        ListNode endSmaller = begSmaller;
        ListNode begLarger = new ListNode(0);
        ListNode endLarger = begLarger;
        
        ListNode pointer = head;
        while(pointer != null)
        {
            if(pointer.val<x)
            {
                endSmaller.next = pointer;
                endSmaller = endSmaller.next;
            }
            else
            {
                endLarger.next = pointer;
                endLarger = endLarger.next;
            }
            pointer = pointer.next;
        }
        endLarger.next = null;
        endSmaller.next = begLarger.next;
        return begSmaller.next;
    }
}

No comments :

Post a Comment