educative.io

The provided solution does not work for nodes not in sequence

Courses
,
#1

Here is a solution that supports nodes not in sequence:


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_sub_list(head, p, q):
  # We need to know the node before p so se can connect it to q after reversing
  p_node_prev = None
  p_node = head

  # Find p_node and p_node_prev
  while p_node.value != p:
    p_node_prev = p_node
    p_node = p_node.next

  # Don't move p_node reference but rather copy reference
  current_head = p_node

  # Reverse from p to q
  prev, next = None, None
  while prev is None or prev.value != q:
    next = current_head.next
    current_head.next = prev
    prev = current_head
    current_head = next

  # prev now points to q_node
  # so for clarity and only that lets assign to a scemanti variable
  q_node = prev

  p_node.next = next
  p_node_prev.next = q_node

  return head


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(6)
  head.next.next.next.next = Node(4)
  head.next.next.next.next.next = Node(5)

  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = reverse_sub_list(head, 2, 4)
  print("Nodes of reversed LinkedList are: ", end='')
  result.print_list()


main()

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5714632037629952

#2

Hello @Demos,

The provided solution returns 1 6 3 2 4 5 for the input 1 2 3 6 4 5 and positions 2 and 4. This is the correct answer. Position 2 to 4 have nodes 2 3 6 which when reversed will become 6 3 2. Your solution returns 1 4 6 3 2 5 for the same inputs which is an incorrect answer. Your solution is reversing the nodes from position 2 to 5 instead of position 2 to 4.

Hope this helps!

#3

My bad @Muhammad_Raahim_Khan I misread the question thinking I neeeded to reverse from the node with value p to the node with value q whereas it was asking reversing nodes from position p to position q.

Here is the updated answer for that solution as well and thanks for pointing that out.


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_sub_list(head, p, q):
  # We need to know the node before p so se can connect it to q after reversing
  p_node_prev = None
  p_node = head

  position = 1
  # Find p_node and p_node_prev
  while position != p:
    p_node_prev = p_node
    p_node = p_node.next
    
    position += 1

  # Don't move p_node reference but rather copy reference
  current_head = p_node

  # Reverse from p to q
  prev, next = None, None
  while position != q + 1:
    next = current_head.next
    current_head.next = prev
    prev = current_head
    current_head = next

    position += 1

  # prev now points to q_node
  # so for clarity and only that lets assign to a scemanti variable
  q_node = prev

  p_node.next = next
  p_node_prev.next = q_node

  return head


def main():
  head = Node(1)
  head.next = Node(2)
  head.next.next = Node(3)
  head.next.next.next = Node(6)
  head.next.next.next.next = Node(4)
  head.next.next.next.next.next = Node(5)

  print("Nodes of original LinkedList are: ", end='')
  head.print_list()
  result = reverse_sub_list(head, 2, 4)
  print("Nodes of reversed LinkedList are: ", end='')
  result.print_list()


main()