-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathreverse block of k nodes linked list.cpp
104 lines (104 loc) · 2.02 KB
/
reverse block of k nodes linked list.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
99
100
101
102
103
104
#include<iostream>
using namespace std;
struct node
{
int data;
node* next;
};
void show(node *head)
{
node *current=head;
cout<<"The list is ";
while(current)
{
cout<<current->data<<" ";
current=current->next;
}
cout<<endl;
}
void insert(node **head, int n)
{
node *link=new node;
link->data=n;
link->next=NULL;
if(!*head)
*head=link;
else
{
node *current = *head;
while(current->next!=NULL)
current=current->next;
current->next=link;
}
show(*head);
}
node* reverse_block(node *start)//reverse the block within list
{
node* current = start;
node* prev = nullptr;
node* next = nullptr;
while(current)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
node* reverse_list(node* head,int k)
{
node *start = nullptr;
node *end = nullptr;
node *next = head;
head = nullptr;
while(next!=NULL)
{
start = next;
end = next;
while(end!=NULL && k-1)
{
end = end->next;
k--;
}
if(end!=NULL)
{
next = end->next;
end->next = nullptr;
start = reverse_block(start);
}
else
{
next = nullptr;
}
if(head==nullptr)
{
head = start;
}
else
{
node *curr = head;
while(curr->next!=NULL)
curr = curr->next;
curr->next = start;
}
}
return head;
}
int main()
{
node *head=NULL;
int n;
int k;
cout<<"Enter the element (0 to end)"<<endl;
while(cin>>n)
if(n)
insert(&head,n);
else
break;
cout<<"Enter the block size"<<endl;
cin>>k;
head=reverse_list(head,k);
show(head);
return 0;
}