-
Notifications
You must be signed in to change notification settings - Fork 1
/
Reverse contiguous even elements.cpp
98 lines (81 loc) · 2.66 KB
/
Reverse contiguous even elements.cpp
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Problem Description
// Given a singly linked list of integers, reverse every contiguous set of nodes that have only even values.
// Input format
// N - An integer denoting the number of nodes in the linked list.
// N integers follow where ith integer denotes the ith node value in the linked list
// Output format
// Return the head of the modified list
// Constraints
// 0 <= N <= 10^5
// -10^9 <= value <= 10^9
// Sample Input 1
// 8
// 1 2 3 3 4 6 8 5
// Sample Output 1
// 1 2 3 3 8 6 4 5
// Explanation 1
// There are two sublists of even elements, which [2] and [4->6->8]. The sublist [4->6->8] has been reversed and the single sublist [2] need not be reversed.
// Sample Input 2
// 6
// 1 3 2 5 4 6
// Sample Output 2
// 1 3 2 5 6 4
// Explanation 2
// There are two sublists of even elements which are [2] and [4 6]. The [4,6] sublist has been reversed and the single sublist [2] need not be reversed. Rest of the odd values remain constant.
//SOLUTION:
/*We create a seperate function for reversing the linked list that contains even elements, the head & tail of the linked list is passed to that function and then
after reversing the list is attached to the original list*/
pair<ListNode*,ListNode*> reverse_even(ListNode* start, ListNode* end)
{
pair<ListNode*,ListNode*> ans;
ListNode *curr=start,*prev=NULL, *nextNode=NULL;
ans.second=curr;
end->next=NULL;
/*we have to keep on reversing untill curr is not NULL as the link of last element also needs to be changesd so we first make end->next NULL before starting reversal*/
while(curr!=NULL)
{
nextNode=curr->next;
curr->next=prev;
prev=curr;
curr=nextNode;
}
ans.first=prev;
return ans;
}
ListNode * reverseEvenElements(ListNode *head) {
if(head==NULL) return NULL;
ListNode *new_head=NULL;
if(head->val%2!=0) new_head=head;
ListNode *curr=head,*prev=NULL;
while(curr!=NULL)
{
if(curr->val%2==0)
{
ListNode *evenhead=curr;
ListNode *eventail;
while(curr!=NULL&&curr->val%2==0)
{
eventail=curr;
// prev=curr; /*the prev is not updated here as we have to attach the even list to the non-even list*/
curr=curr->next;
}
pair<ListNode*,ListNode*>ans=reverse_even(evenhead,eventail);
/*if the first element of list is even, then new_head returned needs to be updated after reversing*/
if(new_head==NULL)
new_head=ans.first;
/*Now , we have to attach the reversed list to our original list.*/
if(prev!=NULL)
{
prev->next=ans.first;
}
ans.second->next=curr;
}
else
{
/*we will update the prev everytime it is odd, as we want prev for attaching it to the even list*/
prev=curr;
curr=curr->next;
}
}
return new_head;
}