Monday 6 June 2016

Reverse merge the half linked list

Write the production level code to arrange the linked list as given example:

1->2->3->4->5->6, make the following changes 1->6->2->5->3->4.

class Node {
     int value; Node next;
     public Node(int value) {
           this.value = value;
     }
}

public class ArrangeSuffledList {
     private static void getReversedSuffledList(Node head) {
           if(head==null || head.next==null) {
                printList(head);
                return;
           }
          
           Node end = head.next;
           int length = 1;
           while(end != null) {
                end = end.next;
                length++;
           }

           Node mid = head.next;
           for (int i = 0; i < length/2-1; i++) {
                mid = mid.next;
           }

           //printList(mid);
           Node head2 = new Node(mid.value);
           Node next = mid.next;

           for (int i = 0; i < length-length/2-1; i++) {
                Node tNext = next.next;
                next = new Node(next.value);
                Node temp = next;
                temp.next = head2;
                head2 = temp;
                next = tNext;       

           }

           printList(mergeList(head, head2, length));

     }

     private static Node mergeList(Node head1, Node head2, int length) {
           Node head = new Node(head1.value);
           head.next = new Node(head2.value);
           Node next = head.next;

           int count = 2;

           head1 = head1.next;
           head2 = head2.next;

           while(head2!=null) {
                Node temp = new Node(head1.value);
                next.next = temp;
                next = next.next;
                count++;
                if(count<length) {
                     temp = new Node(head2.value);
                     next.next = temp;
                     next = next.next;
                     count++;
                }

                head1 = head1.next;
                head2 = head2.next;
           }
           return head;
     }

     public static void main(String[] args) {
           Node head = new Node(1);
           head.next = new Node(2);
           head.next.next = new Node(3);
           head.next.next.next = new Node(4);
           head.next.next.next.next = new Node(5);
           head.next.next.next.next.next = new Node(6);
           //head.next.next.next.next.next.next = new Node(7);

           /* 1->2->3->4->5->6 :: 1->6->2->5->3->4 * */
           getReversedSuffledList(head);
           //printList(head);
     }

     private static void printList(Node head) {
           System.out.println("");
           Node next = null;
           if(head!=null) {
                System.out.print(head.value+" ");
                next = head.next;
           }

           while(next!=null) {
                System.out.print(next.value+" ");
                next = next.next;
           }
     }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...