-
Notifications
You must be signed in to change notification settings - Fork 1.3k
/
swap_nodes_without_swapping_data.py
104 lines (84 loc) · 2.92 KB
/
swap_nodes_without_swapping_data.py
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
# Problem : Given a linked list, and two data values, x and y.
# Goal: Swap the nodes of linkedlist by swapping pointers
# (and not swapping data) such that nodes with data x will contain y and vice versa.
class Node:
"""Representation of a linked list node"""
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
"""Representation of a linked list"""
def __init__(self):
self.head = None
def push(self, data):
"""Pushes new data to the head of the list"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def print_list(self):
"""Prints a linked list"""
itr = self.head
while itr:
if itr.next is None:
print(itr.data)
else:
print(str(itr.data) + '-->', end = ' ')
itr = itr.next
def print_list_addr(self):
"""Prints a list with address of the next pointer"""
itr = self.head
while itr:
if itr.next is None:
print(str(itr.data) + '(' + str(hex(id(itr))) + ')')
else:
print(str(itr.data) + '(' + str(hex(id(itr))) + ') --> ', end=' ')
itr = itr.next
def swap_nodes_without_swapping_data(self, x, y):
"""Swap the nodes of linked without swapping pointers i.e.
swap nodes such that nodes with data x will contain y and vice versa."""
# We are making assumption that nodes in linked list are unique
if x == y:
return
curr_x = self.head
curr_y = self.head
prev_x = None
prev_y = None
# find node with data x
while curr_x and curr_x.data != x:
prev_x = curr_x
curr_x = curr_x.next
# find node with data y
while curr_y and curr_y.data != y:
prev_y = curr_y
curr_y = curr_y.next
# x or y is not there
if curr_x is None or curr_y is None:
return
# if x is not head of the linked list.
if prev_x is not None:
prev_x.next = curr_y
else: # if x was head, make y the head of the linked list.
self.head = curr_y
# if y is not head of the linked list
if prev_y is not None:
prev_y.next = curr_x
else: # if y was head, make x the head of the linked list.
self.head = curr_x
# now swap the next pointers.
temp = curr_x.next
curr_x.next = curr_y.next
curr_y.next = temp
if __name__ == "__main__":
lst = LinkedList()
lst.push(5)
lst.push(1)
lst.push(3)
lst.push(2)
lst.push(4)
print("List before (with and without addr):")
lst.print_list()
lst.print_list_addr()
lst.swap_nodes_without_swapping_data(1, 4)
print("List after (with and without addr):")
lst.print_list()
lst.print_list_addr()