Rearrange nodes of linked list such as odd numbered index-nodes appear last

Question 1

Try this: the code is self-explanatory: If you do not understand, post comment, I will clarify

public void switchPairs() {
    if (front != null && front.next != null) {
        ListNode current = front.next;
        front.next = current.next;
        current.next = front;
        front = current;
        current = current.next;

        while (current.next != null && current.next.next != null) {
            ListNode temp = current.next.next;
            current.next.next = temp.next;
            temp.next = current.next;
            current.next = temp;
            current = temp.next;
        }
    }
}

Question 2

You're thinking in terms of basically re-computing the index into the list after each move.

They're really thinking in terms of moving every other item from the list as it originally existed.

The intended difficulty is simply in keeping track of when to stop rearranging elements. You want to stop after the node that was originally the last in the list, but if you do this the most obvious way, that won't be the last node in the list any more when you get there.

Subtle hint: even assuming a singly-linked list with no way to find the last node directly, you can still do the job with only a single traversal of the list.

Doing this is ever so slightly tricky. Instead of adding each node to the end of the original list as you traverse the first list, you put those nodes together into separate, temporary list while you traverse the original list. When you reach the end of the original list, you then splice the whole temporary list onto the end of the original list by changing the null pointer at the end of the original list to point at the beginning of the temporary list (and since you've reached the end, you set the "next" pointer in the last node of the temporary list to NULL).

This would often be impractical with an array, because you'd temporarily need extra storage for half the elements in the array. With linked lists, however, you only need two extra pointers: one for the beginning of the temporary list, and another to the last node in the temporary list.

Question 3

You made a little mistake in your implementation, you don't want to update temp by doing temp.next=curr.next; every time. You want to keep a variable to the beginning of your list, and then a variable which will be the last element of the list (and you will append the next temp node to this element, and never touch the first element). Then append the first element to the end of the original list.

When you build a list, you always keep 2 two pointers : one on the beginning of the list (so you can use it entirely) and one on the end of the list to add elements. That why you add element in the end in O(1) and you to add element in the n position in O(n) (you need to iterate over the n first element).

Jerry Coffin hinted it in his last paragraph.

Maybe you should see how a list is constructed? http://en.wikipedia.org/wiki/Linked_list (Here I think you are implementing simply linked list.)

Question 4

The piece of code below generates the exact output you asked for. Read the inline comments. Cheers!

/**
 * A method that strips the even and odd elements in a Linkedlist
 */
public static void zipper(LinkedList list) {

    LinkedList head = list;
    LinkedList oddHead = head;
    LinkedList evenHead = head.getNext();

    LinkedList oddMove = oddHead;
    LinkedList evenMove = evenHead;

    while (head != null && evenMove != null && oddMove != null) {

        oddMove.next = head.next.next; // set the link to appropriate
                                        // position for odd list
        oddMove = oddMove.next; // move the pointer to new head of odd list
        head = head.next; // move original head
        if (head != null) {
            evenMove.next = head.next; // set the link to appropriate
                                        // position for even list
            evenMove = evenMove.next; // move the pointer to new head of
                                        // even list
        }

    }

    LinkedList temp2 = oddHead;

    while (temp2.next != null) {
        //System.out.println(temp2.elem);
        temp2 = temp2.next;
    }

    temp2.next = evenHead;


        System.out.println("----------------elems------------------");
    while (oddHead != null) {
        System.out.println(oddHead.elem);
        oddHead = oddHead.next;
    }

    System.out.println("------------------------------------------------");}

Question 5

Here is the Java implementation

public static LinearNode<Integer> seperateEvenAndOddIndexNodes(LinearNode<Integer> head) {
    LinearNode<Integer> prevNode =null, currentNode = head, tail = head, nextNode;
    int length = length(head),index = 0;

    if (length < 3) {
        return head;
    }

    while (tail != null && tail.next() != null) {
        tail = tail.next();         
    }
    while (currentNode != null && index < length) {
        nextNode = currentNode.next();
        if (index % 2 == 1) {
            LinearNode<Integer> temp = currentNode;
            tail.next(temp);
            tail = temp;
            prevNode.next(nextNode);
            currentNode = prevNode;
            temp.next(null);
        }
        prevNode = currentNode;
        currentNode = nextNode;
        index++;
    }

    return head;
}

Here is the unit test cases

@Test
public void seperateEvenAndOddIndexesTest() {
    LinearNode<Integer> head = buildLinkedList(1,2,3,4,5,6);
    head = LinkedListUtil.seperateEvenAndOddIndexNodes(head);
    assertLinkedList(head, 1,3,5,2,4,6);

    head = buildLinkedList(1);
    head = LinkedListUtil.seperateEvenAndOddIndexNodes(head);
    assertLinkedList(head, 1);

    head = buildLinkedList(1, 2);
    head = LinkedListUtil.seperateEvenAndOddIndexNodes(head);
    assertLinkedList(head, 1, 2);

    head = buildLinkedList(1, 2, 3);
    head = LinkedListUtil.seperateEvenAndOddIndexNodes(head);
    assertLinkedList(head, 1, 3, 2);
}

Question 6

Here is a working code of O(n) : Idea is you pass a reference to an empty list q along with original list. slice p->next, append it to list q whose tail always points to the start of original list p. Note this solution is only when even nodes are to be placed before all nodes. You can easily change the logic for vice-versa case.

int main() {

    NODEPTR list = create_list(10);
    NODEPTR q = NULL;  
    odd_even_part(list, &q);

    printf("\n Here is list after partitionining and rearranging :\n");
    recursive_print(q);

    return 0;

}
/* Use recursion to build rearranged list q */

NODEPTR odd_even_part(NODEPTR p, NODEPTR* q) {
    NODEPTR temp = NULL;
    if(p == NULL || p->next == NULL) {
        return p;
    }
    else {
        temp = p->next;
        p->next = temp->next;
        if((*q) == NULL) {
            (*q) = temp;
            temp->next = p;
        }else {
            temp->next = (*q)->next;
            (*q)->next = temp;
        }

        odd_even_part(p->next,&temp);
    }
}

Question 7

This problem can be solved by reorganizing the large list into two smaller lists, one with the even-indexed elements and one with the odd-indexed elements. Once these two sub-lists are created, merge them together and set front to the head of the merged list.

In order to eventually merge the two lists, you'll need four variables. Two variables to point at the front of each sub-list, called evenFront and oddFront, and two variables to iterate through the sub-lists, called even and odd.

Initialize even to front (since the list is zero-indexed, the first even-indexed element in the list is at index zero, also known as front) and initialize odd to front.next (for the same reason, the first odd-indexed element in the list is at index one, the next element after front).

Here is my code.

public void shift() {
    if (front != null && front.next != null) {
        // iterators for the even and odd sub-lists
        ListNode even = front;
        ListNode odd = front.next;
        // pointers for the front of the even and odd sub-lists; these do not change
        ListNode evenFront = even;
        ListNode oddFront = odd;
        while (even.next != null && odd.next != null) {
            even.next = even.next.next;
            even = even.next;
            odd.next = odd.next.next;
            odd = odd.next;
        }
        even.next = oddFront;
        front = evenFront;
    }
}