Home/

...

/

Reverse every K-element Sub-list (medium)

Reverse every K-element Sub-list (medium)

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Reverse every K-element Sub-list (medium) lesson:

Press + to interact
Python 3.5
from __future__ import print_function
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ")
      temp = temp.next
    print()
def reverse_every_k_elements(head, k):
  if k <= 1 or head is None:
    return head
  current, previous = head, None
  while True:
    last_node_of_previous_part = previous
    # after reversing the LinkedList 'current' will become the last node of the sub-list
    last_node_of_sub_list = current
    next = None  # will be used to temporarily store the next node
    i = 0
    while current is not None and i < k:  # reverse 'k' nodes
      next = current.next
      current.next = previous
      previous = current
      current = next
      i += 1
    # connect with the previous part
    if last_node_of_previous_part is not None:
      last_node_of_previous_part.next = previous
    else:
      head = previous
    # connect with the next part
    last_node_of_sub_list.next = current
    if current is None:
      break
    previous = last_node_of_sub_list
  return head
def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(5)
  head.next.next.next.next.next = Node(6)
  head.next.next.next.next.next.next = Node(7)
  head.next.next.next.next.next.next.next = Node(8)
  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = reverse_every_k_elements(head, 3)
  print("Nodes of reversed LinkedList are: ", end='')
  result.print_list()
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample input #1

Linked list: 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> null
k: 3

Iteration No.

Line No.

last_node_

of_previous_part

last_node_

of_sub_list

current,

next,

previous

List Status

-

21

-

-

1,

-,

null

1-->2-->3-->4-->5-->6-->7-->8-->null

1

25

null

1

1,

-,

null

1-->2-->3-->4-->5-->6-->7-->8-->null

1

36

null

1

4,

4,

3

null<--1<--2<--3 4-->5-->6-->7-->8-->null

1

46

null

1

4,

4,

1

3-->2-->1-->4-->5-->6-->7-->8-->null

2

25

1

4

4,

4,

1

3-->2-->1-->4-->5-->6-->7-->8-->null

2

36

1

4

7,

7,

6

3-->2-->1 6-->5-->4 7-->8-->null

2

46

1

4

7,

7,

4

3-->2-->1-->6-->5-->4-->7-->8-->null

3

25

4

7

7,

7,

4

3-->2-->1-->6-->5-->4-->7-->8-->null

3

36

4

7

null,

null,

8

3-->2-->1-->6-->5-->4 8-->7-->null

3

46

4

7

null,

null,

null

3-->2-->1-->6-->5-->4-->8-->7-->null

Sample input #2

Encourage the students to complete the table below for the following input:

Linked list: 11 --> 22 --> 10 --> 20 --> 10 --> 50 --> null
k:2

Iteration No.

Line No.

last_node_

of_previous_part

last_node_

of_sub_list

current,

next,

previous

List Status

-

21

-

-

11,

-,

null

11 --> 22 --> 10 --> 20 --> 10 --> 50 --> null

1

25

null

11

11,

-,

null

11 --> 22 --> 10 --> 20 --> 10 --> 50 --> null

1

36

null

11

10,

10,

22

22-->11 10 --> 20 --> 10 --> 50 --> null

1

46

null

11

10,

10,

11

22-->11-->10 --> 20 --> 10 --> 50 --> null

...

...

...

...

...

...

...

...

...

...

...

...

Step-by-step solution construction

Let’s start with the solution for “Reversing a linked list” from the “Introduction” lesson in this pattern:

Press + to interact
Python 3.5
from __future__ import print_function
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
  def print_list(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ")
      temp = temp.next
    print()
  def print_list_with_backarrow(self):
    temp = self
    nodes = []
    # add values of nodes from the linkedlist to the array "nodes"
    while temp is not None:
      nodes.append(temp.value)
      temp = temp.next
    # print the array "nodes" in the reverse order seperated by "<--"
    for (index,value) in enumerate(reversed(nodes)) :
      if index == 0:
         print("null <--",end=" ")
      else:
         print ("<--",end=" ")
      print(value, end=" ")
  def print_list_with_forwardarrow(self):
    temp = self
    while temp is not None:
      print(temp.value, end=" ") #print node value
      
      temp = temp.next
      if temp is None:
        print("--> null") # if this is the last node, print null at the end
      else:
        print("-->", end=" ") 
    print()
def reverse(head):
  previous, current, next = None, head, None
  index = 0
  while current is not None:
    print("Iteration " + str(index) + ": ",end=" ")
    index +=1
    next = current.next  # temporarily store the next node
    current.next = previous  # reverse the current node
    previous = current  # before we move to the next node, point previous to the current node
    
    current.print_list_with_backarrow()
    
    current = next  # move on the next node
    if current is not None:
      print("   ||   ", end=" ")
      current.print_list_with_forwardarrow()
  return previous
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(8)
  head.next.next.next.next = Node(10)
  print("LinkedList: ", end=" ")
  head.print_list_with_forwardarrow()
  result = reverse(head)
  print("\n\nNodes of reversed LinkedList are:   ", end='')
  result.print_list_with_backarrow()
main()

We can utilize this code to reverse the sub-lists within a linked list. We need to make the following updates:

  • Add a while loop and utilize the code to reverse a linked list for multiple sub-lists. The highlighted lines implement this changed logic:
Press + to interact
Python 3.5
from __future__ import print_function
 
 
class Node:
 def __init__(self, value, next=None):
   self.value = value
   self.next = next
 
 def print_list(self):
   temp = self
   while temp is not None:
     print(temp.value, end=" ")
     temp = temp.next
   print()
 
 def print_list_with_forwardarrow(self):
   temp = self
   while temp is not None:
     print(temp.value, end=" ") #print node value
    
     temp = temp.next
     if temp is None:
       print("--> null") # if this is the last node, print null at the end
     else:
       print("-->", end=" ")
   print()
 
def reverse_every_k_elements(head, k):
 if k <= 1 or head is None:
   return head
 
 current, previous = head, None
 while True:
   next = None  # will be used to temporarily store the next node
   i = 0
   while current is not None and i < k:  # reverse 'k' nodes
     next = current.next
     current.next = previous
     previous = current
     current = next
     i += 1
 
   print("Pointers after reversing k =", k, "elements:")
   print("\t current: "+str(current.value if current is not None  else "null"))
   print("\t next: "+str(next.value if next is not None  else "null"))
   print("\t previous: "+str(previous.value if previous is not None  else "null"))
 
   head = previous
   print("Part of the array reversed is: ", end=" ")
   head.print_list_with_forwardarrow()
 
   if current is None:
     break
 
 return head
 
 
def main():
 head = Node(1)
 head.next = Node(2)
 head.next.next = Node(3)
 head.next.next.next = Node(4)
 head.next.next.next.next = Node(5)
 head.next.next.next.next.next = Node(6)
 head.next.next.next.next.next.next = Node(7)
 head.next.next.next.next.next.next.next = Node(8)
 
 print("The original linked list: ", end='')
 head.print_list_with_forwardarrow()
 result = reverse_every_k_elements(head, 3)
 print("\nReversed linked list, with k = ", 3, ": ", sep='', end='')
 result.print_list_with_forwardarrow()
 
 
main()

As a result of the above modifications, we are able to reverse every K-element sub-list of the linked list in each iteration of the outermost while loop. However, by the end of the process, the entire list is found in simple reversed order. There is an issue with the way we are connecting the reversed sub-lists.

To fix this, we set up two variables last_node_of_previous_part and last_node_of_sub_list to keep track of the last nodes of the previous and current sub-lists respectively.

  1. On line 58 in the code shown below, when the next sub-list gets reversed, we set the next of last_node_of_previous_part to its first element. Note that previous will be pointing to the first element of the reversed sub-list.
  2. On line 63, we set the next of last_node_of_sub_list to the first node of the next sub-list.

Press + to interact
Python 3.5
from __future__ import print_function
 
 
class Node:
 def __init__(self, value, next=None):
   self.value = value
   self.next = next
 
 def print_list(self):
   temp = self
   while temp is not None:
     print(temp.value, end=" ")
     temp = temp.next
   print()
 
 def print_list_with_forwardarrow(self):
   temp = self
   while temp is not None:
     print(temp.value, end=" ") #print node value
    
     temp = temp.next
     if temp is None:
       print("--> null") # if this is the last node, print null at the end
     else:
       print("-->", end=" ")
   print()
 
 
def reverse_every_k_elements(head, k):
 if k <= 1 or head is None:
   return head
 
 current, previous = head, None
 while True:
   last_node_of_previous_part = previous
   # after reversing the LinkedList 'current' will become the last node of the sub-list
   last_node_of_sub_list = current
   print("Pointers to previous and current sub-lists:")
   print("\t last_node_of_previous_part: "+str(last_node_of_previous_part.value if last_node_of_previous_part is not None  else "null"))
   print("\t last_node_of_sub_list: "+str(last_node_of_sub_list.value if last_node_of_sub_list is not None  else "null"))
 
   next = None  # will be used to temporarily store the next node
   i = 0
   while current is not None and i < k:  # reverse 'k' nodes
     next = current.next
     current.next = previous
     previous = current
     current = next
     i += 1
 
   print("Pointers after reversing k =", k, "elements:")
   print("\t current: "+str(current.value if current is not None  else "null"))
   print("\t next: "+str(next.value if next is not None  else "null"))
   print("\t previous: "+str(previous.value if previous is not None  else "null"))
 
   # connect with the previous part
   if last_node_of_previous_part is not None:
     last_node_of_previous_part.next = previous
   else:
     head = previous
 
   # connect with the next part
   last_node_of_sub_list.next = current
 
   head.print_list_with_forwardarrow()
   if current is None:
     break
   previous = last_node_of_sub_list
   print("After updating previous:")
   print("\t Previous: "+str(previous.value if previous is not None  else "null"), "\n")
  
 return head
 
 
def main():
 head = Node(1)
 head.next = Node(2)
 head.next.next = Node(3)
 head.next.next.next = Node(4)
 head.next.next.next.next = Node(5)
 head.next.next.next.next.next = Node(6)
 head.next.next.next.next.next.next = Node(7)
 head.next.next.next.next.next.next.next = Node(8)
 
 print("Nodes of original LinkedList are: ", end='')
 head.print_list_with_forwardarrow()
 result = reverse_every_k_elements(head, 3)
 print("Nodes of reversed LinkedList are: ", end='')
 result.print_list_with_forwardarrow()
 
 
main()

Note that the method print_list_with_forwardarrow is used to print the LinkedList with arrows -->. Students should be encouraged to improve this method themselves to produce console traces that make the working of the code more transparent.