Python Challenge - Swap Elements in a Linked List

This community-built FAQ covers the “Swap Elements in a Linked List” code challenge in Python. You can find that challenge here, or pick any challenge you like from our list.

Top Discussions on the Python challenge Swap Elements in a Linked List

There are currently no frequently asked questions or top answers associated with this challenge – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this challenge. Ask a question or post a solution by clicking reply (reply) below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this challenge, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply (reply) below!
You can also find further discussion and get answers to your questions over in Language Help.

Agree with a comment or answer? Like (like) to up-vote the contribution!

Need broader help or resources? Head to Language Help and Tips and Resources. If you are wanting feedback or inspiration for a project, check out Projects.

Looking for motivation to keep learning? Join our wider discussions in Community

Learn more about how to use this guide.

Found a bug? Report it online, or post in Bug Reporting

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

I chose to swap the .data of the nodes ( instead of swapping the nodes themselves and changing their .next ).

I posted about it here: Python Challenge - Swap Elements in a Linked List - #2 by janbazant1107978602

1 Like

Here’s a new link for that post (where I put that code): Python Challenge - Swap Elements in a Linked List - #2 by janbazant1107978602

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()
from LinkedList import * def swap_nodes(input_list, val1, val2): next_node = input_list while next_node != None: if next_node.data == val1: next_node.data = val2 elif next_node.data == val2: next_node.data = val1 next_node = next_node.next return input_list demo_list = make_linked_list([1, 2, 3, 4, 5, 6]) swap_nodes(demo_list, 2, 5) demo_list.print_linked_list()
2 Likes

I did something similar to the stuff in the previous posts.
I made variables to keep track of the nodes for each of the values, the nodes before those, and the nodes after.
I dealt with 3 possible cases separately: val1 → val2, val2 → val1, and neither
I also had to put in logic for val1 or val2 being at the head of the linked list.
My code is quite long; some of the logic is repeated.

my code
def swap_nodes(input_list, val1, val2):
  if (input_list is None):
    return None
  if ((val1 is None) or (val2 is None)):
    return input_list

  input_list_is_node = isinstance(input_list, Node)
  #head = None

  if (input_list_is_node):
    head = input_list
  else:
    head = input_list.head
  
  before1 = None
  before2 = None
  node1 = None
  node2 = None
  after1 = None
  after2 = None
  
  if (isinstance(val1, Node) and isinstance(val2, Node)):
    node1 = val1
    node2 = val2
  else: 
    current = head
    while(current):
      if (current.data == val1):
        node1 = current
      elif (current.data == val2):
        node2 = current
      current = current.next
    #endwhile
  #endelse

  if ((node1 is None) or (node2 is None)):
    return input_list

  current = head
  while(current):
    if (current.next == node1):
      before1 = current
    elif (current.next == node2):
      before2 = current
    if (current == node1):
      after1 = current.next
    elif(current == node2):
      after2 = current.next
    current = current.next
  #endwhile 

  if (after1 == node2):
    node2.next = node1
    node1.next = after2
    if (before1 is not None):
      before1.next = node2
  elif (after2 == node1):
    node1.next = node2
    node2.next = after1
    if (before1 is not None):
      before2.next = node1
  else:
    node1.next = after2
    node2.next = after1
    if (before1 is not None):
      before1.next = node2
    if (before2 is not None):
      before2.next = node1
  #endelse

  if (node1 == head):
    head = node2
  elif (node2 == head):
    head = node1

  if (input_list_is_node):
    return head
  elif ((node1 == head) or (node2 == head)):
    input_list.head = head
    return input_list
#enddef

Codebyte demonstration:

class Node: def __init__(self, data, next_node=None): self.data = data self.next = next_node #endclass def print_linked_list(self): current = self if (not isinstance(self, Node)): current = self.head while(current): print(current.data, end=" -> ") current = current.next #endwhile print("None") #enddef def make_linked_list(data_list): if (len(data_list) < 1): return None head = None previous = None for data in data_list: current = Node(data) if (previous is None): head = current else: previous.next = current previous = current #endfor return head #enddef def swap_nodes(input_list, val1, val2): if (input_list is None): return None if ((val1 is None) or (val2 is None)): return input_list input_list_is_node = isinstance(input_list, Node) #head = None if (input_list_is_node): head = input_list else: head = input_list.head before1 = None before2 = None node1 = None node2 = None after1 = None after2 = None if (isinstance(val1, Node) and isinstance(val2, Node)): node1 = val1 node2 = val2 else: current = head while(current): if (current.data == val1): node1 = current elif (current.data == val2): node2 = current current = current.next #endwhile #endelse if ((node1 is None) or (node2 is None)): return input_list current = head while(current): if (current.next == node1): before1 = current elif (current.next == node2): before2 = current if (current == node1): after1 = current.next elif(current == node2): after2 = current.next current = current.next #endwhile if (after1 == node2): node2.next = node1 node1.next = after2 if (before1 is not None): before1.next = node2 elif (after2 == node1): node1.next = node2 node2.next = after1 if (before1 is not None): before2.next = node1 else: node1.next = after2 node2.next = after1 if (before1 is not None): before1.next = node2 if (before2 is not None): before2.next = node1 #endelse if (node1 == head): head = node2 elif (node2 == head): head = node1 if (input_list_is_node): return head elif ((node1 == head) or (node2 == head)): input_list.head = head return input_list #enddef demo_list = make_linked_list([1, 2, 3, 4, 5, 6]) print_linked_list(demo_list) swap_nodes(demo_list, 2, 5) print("swap_nodes(demo_list, 2, 5)") print_linked_list(demo_list)

My solution to this problem

from LinkedList import * def swap_nodes(input_list, val1, val2): node1 = input_list while node1 != None: if node1.data == val1: break node1 = node1.next node2 = input_list while node2 != None: if node2.data == val2: break node2 = node2.next if node1 == None or node2 == None: return node1.data = val2 node2.data = val1 return input_list demo_list = make_linked_list([1, 2, 3, 4, 5, 6]) swap_nodes(demo_list, 2, 5) demo_list.print_linked_list()