Techie Delight
Coding made easy
Write an efficient algorithm to reverse the specified portion of a given linked list.
Input:
Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> None
start position = 2
end position = 5
Output: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> None
The problem can be easily solved iteratively by dividing the solution into three parts. To reverse a list from position m to n, you need to:
This can be effectively implemented as following in C++, Java and Python:
C++
|
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
|
#include <iostream>
#include <string>
using namespace std;
// Data Structure to store a linked list node
struct Node
{
int data;
Node* next;
};
// Utility function to print a linked list
void printList(string msg, Node* head)
{
cout << msg;
Node* ptr = head;
while (ptr)
{
cout << ptr->data << ” -> “;
ptr = ptr->next;
}
cout << “NULL” << endl;
}
// Helper function to insert new Node in the beginning of the linked list
void push(Node** head, int data)
{
Node* newNode = new Node();
newNode->data = data;
newNode->next = *head;
*head = newNode;
}
// Iteratively reverse a linked list from position m to n
// Note that the head is passed by reference
void reverse(Node* &head, int m, int n)
{
Node* prev = NULL; // the prev pointer
Node* curr = head; // the main pointer
// 1. Skip the first m nodes
for (int i = 1; curr != NULL && i < m; i++)
{
prev = curr;
curr = curr->next;
}
// prev now points to position the (m-1)’th node
// curr now points to position the m’th node
Node* start = curr;
Node* end = NULL;
// 2. Traverse and reverse the sub-list from position m to n
for (int i = 1; curr != NULL && i <= n – m + 1; i++)
{
// Take note of the next node
Node* next = curr->next;
// move the ‘curr’ node onto the ‘end’
curr->next = end;
end = curr;
// move to the next node
curr = next;
}
// start points to the m’th node
// end now points to the n’th node
// curr now points to the (n+1)’th node
// 3. Fix the pointers and return the head node
start->next = curr;
if (prev != NULL)
{
prev->next = end;
}
// when m = 1 (prev is NULL)
else
{
// fix the head pointer to point to the new front
head = end;
}
}
int main()
{
int m = 2, n = 5;
Node* head = NULL;
for (int i = 7; i >= 1; i—)
push(&head, i);
printList(“Original Linked List: “, head);
reverse(head, m, n);
printList(“Reversed Linked List: “, head);
return 0;
}
|
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL
Reversed Linked List: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> NULL
Java
|
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
|
// A linked list node
class Node {
int data;
Node next;
Node(int data, Node next) {
this.data = data;
this.next = next;
}
}
class Main {
// Utility function to print a linked list
public static void printList(String msg, Node head)
{
System.out.print(msg);
Node ptr = head;
while (ptr != null)
{
System.out.print(ptr.data + ” -> “);
ptr = ptr.next;
}
System.out.println(“null”);
}
// Iteratively reverse a linked list from position m to n
public static Node reverse(Node head, int m, int n)
{
Node prev = null;
Node curr = head;
// 1. Skip the first m nodes
for (int i = 1; curr != null && i < m; i++) {
prev = curr;
curr = curr.next;
}
// prev now points to position the (m-1)’th node
// curr now points to position the m’th node
Node start = curr;
Node end = null;
// 2. Traverse and reverse the sub-list from position m to n
for (int i = 1; curr != null && i <= n – m + 1; i++)
{
// Take note of the next node
Node next = curr.next;
// move the ‘curr’ node onto the ‘end’
curr.next = end;
end = curr;
// move to the next node
curr = next;
}
// start points to the m’th node
// end now points to the n’th node
// curr now points to the (n+1)’th node
// 3. Fix the pointers and return the head node
start.next = curr;
if (prev != null) {
prev.next = end;
} else { // when m = 1 (prev is null)
head = end;
}
return head;
}
public static void main(String[] args)
{
int m = 2, n = 5;
Node head = null;
for (int i = 7; i >= 1; i—) {
head = new Node(i, head);
}
printList(“Original Linked List: “, head);
head = reverse(head, m, n);
printList(“Reversed Linked List: “, head);
}
}
|
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Reversed Linked List: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> null
Python
|
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
|
# A linked list node
class Node:
def __init__(self, data=None, next=None):
self.data = data
self.next = next
# Utility function to print a linked list
def printList(msg, head):
print(msg, end=‘: ‘)
ptr = head
while ptr:
print(ptr.data, end=” -> “)
ptr = ptr.next
print(“None”)
# Iteratively reverse a linked list from position m to n
def reverse(head, m, n):
prev = None
curr = head
# 1. Skip the first m nodes
i = 1
while curr is not None and i < m:
prev = curr
curr = curr.next
i = i + 1
# prev now points to position the (m-1)’th node
# curr now points to position the m’th node
start = curr
end = None
# 2. Traverse and reverse the sub-list from position m to n
while curr is not None and i <= n:
# Take note of the next node
next = curr.next
# move the ‘curr’ node onto the ‘end’
curr.next = end
end = curr
# move to the next node
curr = next
i = i + 1
# start points to the m’th node
# end now points to the n’th node
# curr now points to the (n+1)’th node
# 3. Fix the pointers and return the head node
start.next = curr
if prev is None: # when m = 1 (prev is None)
head = end
else:
prev.next = end
return head
if __name__ == ‘__main__’:
head = None
for i in reversed(range(7)):
head = Node(i + 1, head)
(m, n) = (2, 5)
printList(“Original Linked List”, head)
head = reverse(head, m, n)
printList(“Reversed Linked List”, head)
|
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> None
Reversed Linked List: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> None
Download Run Code
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL
Reversed Linked List: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> NULL
Download Run Code
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Reversed Linked List: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> null
Download Run Code
Output:
Original Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> None
Reversed Linked List: 1 -> 5 -> 4 -> 3 -> 2 -> 6 -> 7 -> None
The time complexity of above solution is O(n) and no extra space is used by the solution.
Exercise: Write recursive version of above solution.
source