The Gateway to Computer Science Excellence

+1 vote

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.

+1 vote

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.

+1

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

0 votes

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

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

let me know if I'm wrong.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,688 answers

199,305 comments

107,325 users