Friday, September 20, 2013

Sort A linked List with N numbers. Range of Numbers in ( 0, 1, 2 )

Sort a Linked List with N numbers. Range of Numbers in this Linked List in ( 0, 1, 2 )

For exmaple:
A Linked List with numbers : { 0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 } OR { 2,0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 }, etc

Below is the Program to sort this:

public class SortALinkedList {

    public Link sort(Link head) {
     
        if (head == null)
            return head;
        if (head.next == null)
            return head;

        Link k = head;
        Link _0 = null;
        Link _1 = null;

        if (head.value() == 0)
            _0 = k;
        else if (head.value() == 1)
            _1 = k;

        Link iter = head.next;
        Link iter_before = head;

        while (iter != null) {

            if (iter.value() == 2) {
                iter_before = iter;
                iter = iter.next;
                continue;
            }

            Link p = iter;
            iter = iter.next;
            iter_before.next = iter;

            if (p.value() == 1) {

                if (_1 == null) {
                    _1 = p;

                    if (_0 != null) {
                        p.next = _0.next;
                        _0.next = p;
                    } else {
                        p.next = head;
                    }
                } else {
                    p.next = _1.next;
                    _1.next = p;
                }

            } else if (p.value() == 0) {

                if (_0 == null) {
                    _0 = p;
                    p.next = (_1 == null ? head : _1);
                } else {
                    p.next = k;
                }
                k = p;
            }

        }

        return k;
    }

    public static void main(String[] args) {

        int[] arr0 = new int[] { 0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr1 = new int[] {  1,0, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr2 = new int[] { 2,1, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr3 = new int[] { 2,0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr4 = new int[] { 2,2,0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr5 = new int[] {  1, 1, 0, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        Link head = Link.build(arr0);

        SortALinkedList srt = new SortALinkedList();
        Link k = srt.sort(head);

        k.print(k);
   
    }

}

1 comment: