Interview Bootcamp

0% completed

​

Solution: Reverse a Sub-list

Problem Statement

Given the head of a LinkedList and two positions ‘p’ and ‘q’, reverse the LinkedList from position ‘p’ to ‘q’.

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= p <= q <= n

Solution

The problem follows the In-place Reversal of a LinkedList pattern. We can use a similar approach as discussed in Reverse a LinkedList. Here are the steps we need to follow:

  1. Skip the first p-1 nodes, to reach the node at position p.
  2. Remember the node at position `p-1

.....

.....

.....

Like the course? Get enrolled and start learning!
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago


#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def reverse(self, head, p, q):
    org_head = head

    # find the p node
    node = head 
    prev_p = None
    count = 1
    while count < p:
      count += 1
      prev_p = node
      node = node.next

    # reverse from p node to the q node 
    prev_q = None
    count = q
    before_reverse = node
    while count >= p:
      count -= 1
      next_node = node.next
      node.next = prev_q
      prev_q = node
      node = next_node
   
    # linking the nodes of the reversed part to the rest of linked list
    if prev_p:
      prev_p.next = prev_q
    else:
      org_head = prev_q # edge case if p = 1 = head node

    if before_reverse:
      before_reverse