forked from Kritika-byte/DSA-for-k
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Reorder List
36 lines (36 loc) · 1013 Bytes
/
Reorder List
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
void reorderList(ListNode* head) {
//Find mid of linked list using fast and slow pointer
ListNode* slow=head, *fast=head;
while(fast!=NULL && fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
//Reverse all the links of the nodes after the middle node
ListNode *prev=slow;
slow=slow->next;
prev->next=NULL;
while(slow)
{
ListNode *temp=slow->next;
slow->next=prev;
prev=slow;
slow=temp;
}
//Place the fast pointer on head and slow pointer at the end node
fast=head;
slow=prev;
//Put the slow node in between fast and fast->next alternatively
while(slow->next)
{
ListNode *fasttemp=fast->next;
ListNode *slowtemp=slow->next;
fast->next=slow;
slow->next=fasttemp;
slow=slowtemp;
fast=fasttemp;
}
}
};