Home/

...

/

Problem Challenge 2

Problem Challenge 2

Dry-run templates

This is the implementation of the solution provided for the problem posed in Problem Challenge 2 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 rotate(head, rotations):
  if head is None or head.next is None or rotations <= 0:
    return head
  # find the length and the last node of the list
  last_node = head
  list_length = 1
  while last_node.next is not None:
    last_node = last_node.next
    list_length += 1
  last_node.next = head  # connect the last node with the head to make it a circular list
  rotations %= list_length  # no need to do rotations more than the length of the list
  skip_length = list_length - rotations
  last_node_of_rotated_list = head
  for i in range(skip_length - 1):
    last_node_of_rotated_list = last_node_of_rotated_list.next
  # 'last_node_of_rotated_list.next' is pointing to the sub-list of 'k' ending nodes
  head = last_node_of_rotated_list.next
  last_node_of_rotated_list.next = None
  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)
  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = rotate(head, 3)
  print("Nodes of rotated 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: 11 --> 22 --> 33 --> 44 --> 55 --> 66 --> null
k: 3

Iteration No.

Line no.

head

last_node

list_length

rotations

skip_length

last_node_of_rotated_list

-

22-23

11

11

1

3

-

-

1

24-26

11

22

2

3

-

-

2

24-26

11

33

3

3

-

-

3

24-26

11

44

4

3

-

-

4

24-26

11

55

5

3

-

-

5

24-26

11

66

6

3

-

-

-

29-31

11

66

6

3

3

11

1

32-33

11

66

6

3

3

22

2

32-33

11

66

6

3

3

33

3

32-33

11

66

6

3

3

44

-

36-37

55

66

6

3

3

44

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

Sample Input #2

Linked List: 3 --> 5 --> 7 --> 9 --> null
k: 8

Iteration No.

Line no.

head

last_node

list_length

rotations

skip_length

last_node_of_rotated_list

-

22-23

3

3

1

8

-

-

1

24-26

3

5

2

8

-

-

2

24-26

3

7

3

8

-

-

3

24-26

3

9

4

8

-

-

-

29-31

3

9

4

0

4

3

1

32-33

3

9

4

0

4

5

2

32-33

3

9

4

0

4

7

3

32-33

3

9

4

0

4

9

-

36-37

3

9

4

0

4

9

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

...

Step-by-step solution construction

We need to rotate the linked list by length of the linked list % rotations. Hence, as a first step, we need to traverse the list and calculate the length. In the following code, we are traversing the list on lines 22-31 and incrementing list_length in each iteration.

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 rotate(head, rotations):
  if head is None or head.next is None or rotations <= 0:
    return head
  # find the length and the last node of the list
  last_node = head
  list_length = 1
  iteration = 0
  print("Calculating list length:")
  while last_node.next is not None:
    print("iteration: "+ str(iteration))
    print("\tlast_node: " + str(last_node.value))
    print("\tlist_length: " + str(list_length)) 
    last_node = last_node.next
    list_length += 1
    iteration += 1
  print("LinkedList Length: " + str(list_length))
  
  return head
def main():
  head = Node(11)
  head.next = Node(22)
  head.next.next = Node(33)
  head.next.next.next = Node(44)
  head.next.next.next.next = Node(55)
  head.next.next.next.next.next = Node(66)
  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = rotate(head, 8)
  print("Nodes of rotated LinkedList are: ", end='')
  result.print_list()
main()

In the code below, we are performing the following steps:

  • On line 34, we are connecting the last node of the linked list to the first node (head).

Note: In this step, we cannot call the print_list method from the main function as the list has become circular and the method will never terminate.

  • On line 35, we calculate the required number of rotations by taking the modulus with the size of the list computed in the previous step.

  • On line 36, we calculate the required number of nodes to skip to perform the rotation of the nodes from the end of the 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 rotate(head, rotations):
  if head is None or head.next is None or rotations <= 0:
    return head
  # find the length and the last node of the list
  last_node = head
  list_length = 1
  iteration = 0
  print("Calculating list length:")
  while last_node.next is not None:
    print("iteration: "+ str(iteration))
    print("\tlast_node: " + str(last_node.value))
    print("\tlist_length: " + str(list_length)) 
    last_node = last_node.next
    list_length += 1
    iteration += 1
  print("LinkedList Length: " + str(list_length))
  last_node.next = head  # connect the last node with the head to make it a circular list
  rotations %= list_length  # no need to do rotations more than the length of the list
  skip_length = list_length - rotations # no. of nodes to skip to rotate the elements at the end of the list
  last_node_of_rotated_list = head
  print("Rotations: "+str(rotations))
  print("skip_length: "+str(skip_length))
  print("last_node_of_rotated_list: "+str(last_node_of_rotated_list.value))
  
  print("head: "+str(head.value))
  return head
def main():
  head = Node(11)
  head.next = Node(22)
  head.next.next = Node(33)
  head.next.next.next = Node(44)
  head.next.next.next.next = Node(55)
  head.next.next.next.next.next = Node(66)
  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = rotate(head, 8)
  #print("Nodes of rotated LinkedList are: ", end='')
  #result.print_list()
main()

Until now, we have set up the following:

  1. skip_length: the number of nodes to skip from the left
  2. Made the list circular: connected the last node of the list to the head

We need to write code to skip skip_length nodes from the head (lines 44-45), set head to point to the front of the list (line 51) and set the last skipped node’s next to None (line 52) .

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 rotate(head, rotations):
  if head is None or head.next is None or rotations <= 0:
    return head
  # find the length and the last node of the list
  last_node = head
  list_length = 1
  iteration = 0
  print("Calculating list length:")
  while last_node.next is not None:
    print("iteration: "+ str(iteration))
    print("\tlast_node: " + str(last_node.value))
    print("\tlist_length: " + str(list_length)) 
    last_node = last_node.next
    list_length += 1
    iteration += 1
  print("LinkedList Length: " + str(list_length))
  last_node.next = head  # connect the last node with the head to make it a circular list
  rotations %= list_length  # no need to do rotations more than the length of the list
  skip_length = list_length - rotations
  last_node_of_rotated_list = head
  print("Rotations: "+str(rotations))
  print("skip_length: "+str(skip_length))
  print("last_node_of_rotated_list: "+str(last_node_of_rotated_list.value))
  iteration = 0
  for i in range(skip_length - 1):
    last_node_of_rotated_list = last_node_of_rotated_list.next
    print("iteration: "+ str(iteration))
    print("last_node_of_rotated_list: "+str(last_node_of_rotated_list.value))
    iteration += 1
  # 'last_node_of_rotated_list.next' is pointing to the sub-list of 'k' ending nodes
  head = last_node_of_rotated_list.next
  last_node_of_rotated_list.next = None
  print("head: "+str(head.value))
  return head
def main():
  head = Node(11)
  head.next = Node(22)
  head.next.next = Node(33)
  head.next.next.next = Node(44)
  head.next.next.next.next = Node(55)
  head.next.next.next.next.next = Node(66)
  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = rotate(head, 8)
  print("Nodes of rotated LinkedList are: ", end='')
  result.print_list()
main()