Wednesday, December 24, 2014

Partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

Q. Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

Example

Input:

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Partition around 9

Output:

8 7 6 5 4 3 2 1 0 9 10 

Algorithm:

1. Maintain two pointers T and R. T points to head.
2. If T has value less than partition value PV, then check next node (T advances).
3. If T has value greater than or equal to PV, then pointer R starts from next to T and finds an element whose value is less than PV. If it does not find any such value, it checks if it had encountered value equal to PV anywhere. If there is such a value, node values are swapped. If there is no such value and a value less than PV has not been found, the required work has already been done so it returns from the function call.

Source:

import java.util.Arrays;

public class Code{ 
    public static <T extends Comparable<T>> void partitionList(LinkedList<T> ll, T value){
        LinkedList<T>.Node turtle = ll.head, rabbit, equal = null;
        
        while(turtle!=null){  
            if(turtle.value.compareTo(value) >= 0){
                rabbit = turtle.next;
                int compare;
                equal = null;
                while(rabbit!= null && (compare = rabbit.value.compareTo(value)) >= 0){
                    if(compare==0) equal = rabbit;
                    rabbit = rabbit.next;
                }
                if(rabbit == null){
                    if(equal==null)return;
                    else{ 
                      T temp = equal.value;
                      equal.value = turtle.value;
                      turtle.value = temp;
                    }
                }else{ 
                    T temp = rabbit.value;
                    rabbit.value = turtle.value;
                    turtle.value = temp;
                }
            }
            turtle = turtle.next;
        } 
    }
    
    public static <T> LinkedList<T> buildList(T[] a){ 
        LinkedList<T> ll = new LinkedList<>();
        for(T t:a){ll.add(t);}
        return ll;
    }
    
    public static void test(Integer[] array, int number){
        System.out.println("\n"+Arrays.toString(array));
        System.out.println("Partitioning around "+number);
        LinkedList<Integer> ll = buildList(array); 
        partitionList(ll, number);
        System.out.println(ll); 
    }
    
    public static void main(String[] args){
        Integer array[] = new Integer[]{10,9,8,7,6,5,4,3,2,1,0};
        test(array, 9);
        
        array = new Integer[]{5,2,7,3,9,1,3,6,4,8};
        test(array, 3);
        
        array = new Integer[]{5,2,7,3,9,1,0,6,4,8};
        test(array, 3); 
        
        array = new Integer[]{0,1,2,3,4,5,6,7,8,9};
        test(array, 3);
        
        array = new Integer[]{2,5,6,2,5,7,9,9,4,3,5,6,8,9,5,3,2,11,3,4,5,6,7,8,9,6,5,6,8,9,1,0};
        test(array, 6);
        
        array = new Integer[]{};
        test(array, 0);
    } 
}


public class LinkedList <T>{
    
    Node head;
    
    class Node{
        Node next;
        T value;
        
        Node(T value){this.value = value;}
    }
    
    public void add(T value){
        if(head==null){head = new Node(value); return;}
        Node t = head;
        while(t.next!=null){t = t.next;}
        t.next = new Node(value); 
    }
    
    public boolean isEmpty(){
        return head==null;
    }
    
    @Override
    public String toString(){
        StringBuilder bf = new StringBuilder();
        Node t = head;
        while(t!=null){
            bf.append(t.value);
            t = t.next;
        }
        return bf.toString();
    }
}

Output:

[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
Partitioning around 9
8 7 6 5 4 3 2 1 0 9 10 

[5, 2, 7, 3, 9, 1, 3, 6, 4, 8]
Partitioning around 3
2 1 3 3 9 5 7 6 4 8 

[5, 2, 7, 3, 9, 1, 0, 6, 4, 8]
Partitioning around 3
2 1 0 3 9 5 7 6 4 8 

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Partitioning around 3
0 1 2 3 4 5 6 7 8 9 

[2, 5, 6, 2, 5, 7, 9, 9, 4, 3, 5, 6, 8, 9, 5, 3, 2, 11, 3, 4, 5, 6, 7, 8, 9, 6, 5, 6, 8, 9, 1, 0]
Partitioning around 6
2 5 2 5 4 3 5 5 3 2 3 4 5 5 1 0 6 6 6 6 6 8 7 8 9 9 9 11 8 9 9 7 

[]

Partitioning around 0

No comments:

Post a Comment