I tried to do it without swapping the .data
this time … dealing with the edge case of the nodes that are being switched being “adjacent” to each other caused some trouble, but I figured it out eventually.
The function returns the head node (possibly the new head node, if the head node was swapped).
I used a generator function to deal with the iteration through the nodes of the linked list.
from LinkedList import *
def linked_list_iterator(head_node):
# generator function for iterating through all nodes
yield head_node
current = head_node
while hasattr(current, "next") and current.next is not None:
yield current.next
if (current != current.next):
current = current.next
else:
break
def swap_nodes(input_list, val1, val2):
head_node = input_list
have_node1 = False
have_node2 = False
previous = None
previous1 = None
previous2 = None
for node in linked_list_iterator(head_node):
if (not have_node1) and (node.data == val1):
node1 = node
previous1 = previous
have_node1 = True
elif (not have_node2) and (node.data == val2):
node2 = node
previous2 = previous
have_node2 = True
elif (have_node1 and have_node2):
break
previous = node
if have_node1 and have_node2:
# swap the .next
temp = node1.next
node1.next = node2.next
node2.next = temp
# edge cases: node1 and node2 were adjacent
if (node1.next == node1):
node1.next = node2
elif (node2.next == node2):
node2.next = node1
# update previous nodes' .next
if previous1 is None:
# node1 had no previous, so node2 is now head
head_node = node2
elif (previous1 is not node2) and (previous1 is not node1):
# node that was previous to node1 should be previous to node2
previous1.next = node2
if previous2 is None:
# node2 had no previous, so node1 is now head
head_node = node1
elif (previous2 is not node1) and (previous1 is not node2):
# node that was previous to node2 should be previous to node1
previous2.next = node1
return head_node
demo_list = make_linked_list([1, 2, 3, 4, 5, 6])
swap_nodes(demo_list, 2, 5).print_linked_list()
I also tried to modify that to work with a Linked List class:
def linked_list_iterator(head_node):
# generator function for iterating through all nodes
yield head_node
current = head_node
while hasattr(current, "next") and current.next is not None:
yield current.next
if (current != current.next):
current = current.next
else:
break
class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node
def print_linked_list(self):
for node in linked_list_iterator(self):
print(node.data)
#end of Node class
class LinkedList:
def __init__(self, head_node):
self.head = head_node
@property #getter
def next(self):
if hasattr(self.head, "next"):
return self.head.next
@property #getter
def data(self):
if hasattr(self.head, "data"):
return self.head.data
def print_linked_list(self):
for node in linked_list_iterator(self.head):
print(node.data)
def __iter__(self):
return (node.data for node in linked_list_iterator(self.head))
#end of LinkedList class
def make_linked_list(data_list):
previous = None
current = None
head = None
for x in data_list:
current = Node(x)
if previous is not None:
previous.next = current
else:
head = current
previous = current
#return head
return LinkedList(head)
def swap_nodes(input_list, val1, val2):
if isinstance(input_list, Node):
head_node = input_list
elif isinstance(input_list, LinkedList):
head_node = input_list.head
have_node1 = False
have_node2 = False
previous = None
previous1 = None
previous2 = None
for node in linked_list_iterator(head_node):
if (not have_node1) and (node.data == val1):
node1 = node
previous1 = previous
have_node1 = True
elif (not have_node2) and (node.data == val2):
node2 = node
previous2 = previous
have_node2 = True
elif (have_node1 and have_node2):
break;
previous = node
if have_node1 and have_node2:
# swap the .next
temp = node1.next
node1.next = node2.next
node2.next = temp
# edge cases: node1 and node2 were adjacent
if (node1.next == node1):
node1.next = node2
elif (node2.next == node2):
node2.next = node1
# update previous nodes' .next
if previous1 is None:
# node1 had no previous, so node2 is now head
head_node = node2
elif (previous1 is not node2) and (previous1 is not node1):
# node that was previous to node1 should be previous to node2
previous1.next = node2
if previous2 is None:
# node2 had no previous, so node1 is now head
head_node = node1
elif (previous2 is not node1) and (previous1 is not node2):
# node that was previous to node2 should be previous to node1
previous2.next = node1
if isinstance(input_list, LinkedList):
input_list.head = head_node
return input_list
else:
return LinkedList(head_node)
return head_node
demo_list = make_linked_list([1, 2, 3, 4, 5, 6])
swap_nodes(demo_list, 2, 5)
demo_list.print_linked_list()