recategorized by
918 views
0 votes
0 votes
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
recategorized by

4 Answers

1 votes
1 votes

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.

edited by
1 votes
1 votes
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
0 votes
0 votes
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.
0 votes
0 votes

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.

Related questions

1 votes
1 votes
1 answer
3