Rearrange the nodes of a linked list

Given a linked list, rearrange the node of the list as shown below:

INPUT LIST: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
OUTPUT: 1 -> 8 -> 2 -> 7 -> 3 -> 6 -> 4 -> 5
INPUT LIST: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
OUTPUT: 1 -> 7 -> 2 -> 6 -> 3 -> 5 -> 4

Your solution should be in-place using constant extra memory.

Solution:
The solution to this problem has 3 parts
Part-1:

Divide the list into two equal parts (If there are odd number of nodes, then first half has an extra node)

Part-2:

Reverse the second part list (the one pointed to by h2)

Part-3: 

Perform alternate-Merge on the two small linked lists pointed to by h1 and h2.

Now let us try to write the code for each part of the solution. I am writing the code in Java in this post. The Node of a linked list is defined as below:

class Node{
    int data;
    Node next;
    public Node(int x){
        data = x; next =null;
    }
}

We have added a constructor in the Node to make the creation of the list easy. The given list can now be easily created using below function:

    public Node createList(){
        Node h = new Node(1);
        h.next = new Node(2);
        h.next.next = new Node(3);
        h.next.next.next = new Node(4);
        h.next.next.next.next = new Node(5);
        h.next.next.next.next.next = new Node(6);
        h.next.next.next.next.next.next = new Node(7);
        h.next.next.next.next.next.next.next = new Node(8);
        return h;
    }

Now we have create the list, we can verify the list is created fine using a helper function that create the list

public void printlist(Node h)
{
    System.out.println();
    for(Node temp = h; temp != null; temp = temp.next)
        System.out.print(temp.data+" ");
}

Let us now try to write code for each part of the solution
Code for Part-1:

To break the list in two parts, we first need to find the middle element in the list. We are using the logic given in this post to get to the middle element.

// BREAK THE LIST IN TWO PARTs.
// THE HEAD OF SECOND LIST IS RETURNED & THE HEAD OF FIRST IS UNCHANGED
public Node breakInTwo(Node h)
{
    Node h1, prev;
    prev = h1= h;
    while(h != null)
    {
        prev = h1;
        h1 = h1.next;
        h = h.next;
        if(h != null){ h = h.next; }
    }
    prev.next = null;
    return h1;
}

Code for Part-2:

We already know the code to reverse a linked list. In this post we have written the non-recursive code to reverse a linked list. The post has code in C++, let us write a similar code in Java

public Node reverse(Node h)
{
    if(h == null || h.next == null){ return h; }
    Node a, b, c;
    a = null;
    b = h;
    c = h.next;
    while(b != null)
    {
        b.next = a;
        a = b;
        b = c;
        if(c != null){ c = c.next;}
    }
    return a;
}

Code for Part-3:

Alternate merge is a simple code where we pick the node alternately from each list and append it to the new list in-place. We haev discussed this logic in this post.

But in this case, we know that the two lists have same number of node (with exception of one node). So we can do with a much simpler version.

// MERGE THE TWO LISTS POINTED TO BY h1 AND h2.
// IT DOES NOT MERGE IN A SORTED ORDER, BUT, PUT
// NODES FROM ALTERNATE LISTS IN THE FINAL LIST
// h1 WILL BE THE HEAD OF FINAL LIST
public void alternateMerge(Node h1, Node h2)
{
    while(h1 != null && h2 != null)
    {
        Node temp = h1.next;
        h1.next = h2;
        h1 = temp;
        temp = h2.next;
        h2.next = h1;
        h2 = temp;
    }
}

Now let us just combine these three parts sequentially in a wrapper function

    public void splitAlternate(Node h)
    {
        if(h == null || h.next == null || h.next.next == null){ return; }
        Node h1, h2;
        h1 = h;
        h2 = breakInTwo(h);
        h2 = reverse(h2);  // REVERSE SECOND PART
        alternateMerge(h1, h2);
    }

Below is the complete running program for some lazy people like me :):

public class RTDemo {
    class Node{
        public int data;
        public Node next;
        public Node(int x){
            data = x; next =null;
        }
    }
    // CREATING A SAMPLE LIST
    public Node createList(){
        Node h = new Node(1);
        h.next = new Node(2);
        h.next.next = new Node(3);
        h.next.next.next = new Node(4);
        h.next.next.next.next = new Node(5);
        h.next.next.next.next.next = new Node(6);
        h.next.next.next.next.next.next = new Node(7);
        h.next.next.next.next.next.next.next = new Node(8);
        return h;
    }
    // HELPER FUNCTION: PRINT THE LIST
    public void printlist(Node h)
    {
        System.out.println();
        for(Node temp = h; temp != null; temp = temp.next)
            System.out.print(temp.data+" ");
    }
    public Node reverse(Node h)
    {
        if(h == null || h.next == null){ return h; }
        Node a, b, c;
        a = null;
        b = h;
        c = h.next;
        while(b != null)
        {
            b.next = a;
            a = b;
            b = c;
            if(c != null){ c = c.next;}
        }
        return a;
    }
    // BREAK THE LIST IN TWO PARTs.
    // THE HEAD OF SECOND LIST IS RETURNED & THE HEAD OF FIRST IS UNCHANGED
    public Node breakInTwo(Node h)
    {
        Node h1, prev;
        prev = h1= h;
        while(h != null)
        {
            prev = h1;
            h1 = h1.next;
            h = h.next;
            if(h != null){ h = h.next; }
        }
        prev.next = null;
        return h1;
    }
    // MERGE THE TWO LISTS POINTED TO BY h1 AND h2.
    // IT DOES NOT MERGE IN A SORTED ORDER, BUT, PUT
    // NODES FROM ALTERNATE LISTS IN THE FINAL LIST
    // h1 WILL BE THE HEAD OF FINAL LIST
    public void alternateMerge(Node h1, Node h2)
    {
        while(h1 != null && h2 != null)
        {
            Node temp = h1.next;
            h1.next = h2;
            h1 = temp;
            temp = h2.next;
            h2.next = h1;
            h2 = temp;
        }
    }
    public void splitAlternate(Node h)
    {
        if(h == null || h.next == null || h.next.next == null){ return; }
        Node h1, h2;
        h1 = h;
        h2 = breakInTwo(h);
        h2 = reverse(h2);  // REVERSE SECOND PART
        alternateMerge(h1, h2);
    }
    public static void main(String[] args)
    {
        RTDemo obj = new RTDemo();
        Node head = obj.createList();
        obj.printlist(head);
        obj.splitAlternate(head);
        System.out.println("\nFINAL LIST: ");
        obj.printlist(head);
    }
}