-
Notifications
You must be signed in to change notification settings - Fork 2
/
kth_node_from_end.cpp
183 lines (156 loc) · 3.99 KB
/
kth_node_from_end.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/*
midpoint of the linked list, ie the middle node in a single iteration
1 2 3 4, node 2 will be the middle node
1 2 3 4 5, node 3 is the middle node
fast and slow pointer,
fast will take 2 steps and slow will take 1 step.
fast = 2x slow
*/
/*
overload << and >>.
cin >> head; // insert at the tail of the linked list
cout << head; // print entire linked list
*/
#include <iostream>
using namespace std;
class node {
public:
int data;
node *next;
node(int data) {
this->data = data;
next = NULL;
}
};
// length of the linked list
// head pointer passed by value
int lengthOfList(node *head) {
int count = 0;
while(head != NULL) {
count++;
head = head->next;
}
return count;
}
// for interview purpose, we will define separate functions ie. procedural programming
// head pointer is passed by reference, updating head will reflect in the actual changes.
void insertAtHead(node *&head, int data) {
if(head == NULL) {
head = new node(data);
return;
}
node *temp = new node(data);
temp->next = head;
head = temp;
}
void insertAtTail(node *&head, int data) {
if(head == NULL) {
head = new node(data);
return;
}
node *tail = head;
while(tail->next != NULL) {
tail = tail->next;
}
tail->next = new node(data);
}
// insert at index 'pos' in the linked list
void insertInMiddle(node *&head, int data, int pos) {
// if position = 0, insert at head, if p > length of list, insert at the index.
// corner cases
if(head == NULL or pos == 0)
insertAtHead(head, data);
else if(pos > lengthOfList(head))
insertAtTail(head, data);
else {
// take p - 1 jumps from the head node.
node *ptr = head;
for(int i = 1; i <= pos - 1; i++)
ptr = ptr->next;
node *temp = new node(data);
temp->next = ptr->next;
ptr->next = temp;
}
}
// head pointer passed by value, changes won't be reflected outside the function
void printList(node *head) {
while(head != NULL) {
cout << head-> data << " ";
head = head->next;
}
}
// linear search is the only option
bool searchList(node *head, int key) {
while(head != NULL) {
if(head->data == key)
return true;
head = head->next;
}
return false;
}
// take user input from input text file.
node* inputFile() {
int data;
node *head = NULL;
while(cin >> data) {
insertAtTail(head, data);
}
return head;
}
// take user input from the console
node* inputList() {
int data;
cin >> data;
node*head = NULL;
while(data != -1) {
insertAtTail(head, data);
cin >> data;
}
return head;
}
// operator overloading to print the linked list.
// ostream --> cout
ostream& operator<<(ostream &cout, node *head) {
printList(head);
cout << endl;
return cout;
}
// operator overloading to input a linked list
// istream --> cin
istream& operator>>(istream &cin, node *&head) {
head = inputList();
return cin;
}
node* kth_node_end(node *head, int k) {
node *slow = head, *fast = head;
// move fast pointer k steps ahead
// fast in the condition means fast != NULL
int i = 0;
for(; fast and i < k; i++)
fast = fast->next;
// if k > number of nodes in the list
if(fast == NULL and i == k)
return head;
else if(fast == NULL and i != k)
return NULL;
// move both the pointers one step ahead.
while(fast != NULL) {
fast = fast->next;
slow = slow->next;
}
return slow;
}
int main() {
int k;
node *head;
cin >> head;
cout << "original list: " << head;
cout << "Enter the value of K: ";
cin >> k;
node *ptr = kth_node_end(head, k);
if(ptr == NULL)
cout << "kth node: NULL" << endl;
else
cout << "kth node: " << ptr->data << endl;
return 0;
}