How to manipulate the given linked list in the following manner in O(n) time ?

Question

If we are given a linked list then we have to manipulate such that even indexed node are arranged together and odd
indexed nodes are arranged together after even indexed nodes

for instance the given linked list is 1-->2-->3-->4-->5-->6 , so the op should be

2-->4-->6-->1-->3-->5

Answer 1

Firstly we place a pointer at middle element of the link list.This can be done in n/2 or O(n) by

initially keeping two pointers pointing to start node.Incrementing one ptr by 1(let say p=p->next) and other by 2(let say q=q->next->next) till (q!=null && q->next!=null&& q->next->next!=null).When this loop terminates ptr p will be at middle of link list(LL).

This middle node will be even numbered node if there are even no. of node in LL.Now we need to increment p by 1 and need a new ptr (let say odd) which points to starting node.After this we just need to swap the data (of node to which ptrs are pointing ) and increment both ptrs( odd and p) by 2 .

If no. of nodes in LL are odd then the (extra)increment of p by 1 which was done previously is not needed . 

finding if LL contains even or node no. of nodes can be done in the same loop which is used to find middle ele of LL .So no extra time required.

pls correct me if I am wrong.

Answer 2

p = LL->HEAD 
odd=p
p = p->NEXT
even = p
p = p->NEXT
while(p!=NULL)
{ 
    odd->next = p
    p=p->NEXT 
    odd = odd->next
    even->next = p 
    p=p->NEXT 
    even = even->next 
}

even->next = odd_orig
LL->HEAD = even_orig

Answer 3

Traverse from left to right maintaining two pointers- even and odd. even pointer stops at first odd number (with the pointer to it) and odd pointer stops at first even number. Now, swap them. Continue doing till we finish the list for one of the pointers.

Comments

Sir , initially both odd and even pointer will be pointing to first node .Now If I have the list 1-->2-->3-->4-->5-->6 , Now initially odd pointer stops at node 2 and then we swap 1 and 2 , now the list becomes 2-->1-->3-->4-->5-->6 . Now even pointer is still at node 2 and odd pointer incremented , so now even will stop at node 1 and off will stop at 4 , so which one to swap first , since after swapping i will be having the result as 2-->4-->3-->1-->5-->6 but we want 2-->4-->1-->3-->5-->6

---

yes, my algorithm won't preserve the order. If you want to preserve the order, traverse using a pointer, remove any odd element from the list and add to a new list and finally add the head of this new list at end of the original list.

Answer 4

Given List : 4->7->3->2

1. Go to last node of given list. (let the t points to 2)
2. lstptr = t;
3. Traverse list from head to lstptr. While traversing if node.data is odd. Put it at the end of list.
4. t = t-> next

let me know if I'm wrong.

Comments

we dont have to disturb the order of odd-indexed nodes

---

Ohh. My answer is if data is odd. I reread the question, It seems some what ambiguous. It says : "odd indexed nodes are arranged together after even indexed nodes"  so if we start with index 0 in given example : 

                      1-->2-->3-->4-->5-->6

 index:            0     1    2     3     4     5

so the output should be :

                      1->3->5->2->4->6

---

start indexing from 1 and then we will have nodes like 2-->4-->6-->1-->3-->5