/
swapNodes.py
39 lines (35 loc) · 1.16 KB
/
swapNodes.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
'''
Given a linked list and two keys in it, swap nodes for two given keys.
Nodes should be swapped by changing links.
Example:
Input: 10->15->12->13->20->14, x = 12, y = 20
Output: 10->15->20->13->12->14
You can assume that the list always contains two nodes.
'''
from linkedlist import Node
from linkedlist import LinkedList
def swapNodes(l, x, y):
current, prev, prevX, prevY, nodeX, nodeY = l.head, None, None, None, None, None
while current:
if current.data == x:
prevX = prev
nodeX = current
if current.data == y:
prevY = prev
nodeY = current
prev = current
current = current.next
# case: nodeX is head
if not prevX:
l.head, nodeY.next, prevY.next, nodeX.next = nodeY, nodeX.next, nodeX, nodeY.next
# case: nodeY is head
elif not prevY:
l.head, nodeX.next, prevX.next, nodeY.next = nodeX, nodeY.next, nodeY, nodeX.next
# both are internal nodes
else:
prevX.next, prevY.next, nodeX.next, nodeY.next = nodeY, nodeX, nodeY.next, nodeX.next
l = LinkedList()
[l.append(i) for i in range(1, 8)]
l.printList()
swapNodes(l, 1, 7)
l.printList()