Grokking the Coding Interview: Patterns for Coding Questions
Vote

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’.

Why this is an In-place Reversal of a Linked List problem

What the question saysThe signal it matches
"Given the head of a LinkedList and two positions"the input is a linked list
"reverse the LinkedList from position" p "to" qthe wording says reverse, and only part of the list must change
walking to p, collecting values to q, and writing them backyour first idea is to copy the values into an array

.....

.....

.....

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
Faraz Ahmed

Faraz Ahmed

· 2 years ago

head = prev is used to update the head of the linked list when p === 1, i.e., when we are reversing the sublist starting from the very beginning of the original list.

When p === 1, it means that the sublist we are reversing starts from the very beginning of the original linked list. In this case, after reversing, the head of the sublist becomes the new head of the entire list. Therefore, prev will hold the reference to the new head of the list after the reversal.

When p !== 1, last_node_of_first_part will hold the reference to the node just before the sublist we are reversing. In this case, we will update the next pointer of last_node_of_first_part to point to prev, which is the new head of the reversed sublist. So, in the case where p === 1, we update head to prev because pre

S

sathitsak

· 3 years ago

I think the author should add contraint to this solution

Show 1 reply
A

Aniket Joshi

· 3 years ago

It would have been a completely different problem had there been a detail provided as to how is indexing in the list is being done, i.e. is it 1-based or 0-based like an array.

A

Azimul Haque

· 4 years ago

For python version, why are we assigning current to last_node_of_sub_list.next in the end? This is a bit confusing. I understand last_node_of_sub_list is last part. Should we need to attach it at end?

And why are we returning head? Aren't we doing all calculations in the last_node_of_sub_list, 'last_node_of_first_part', current, and previous? How will the head get updated by itself?

Show 1 reply
C

Clodoaldo Favaro

· 4 years ago

Mine was a little different:

class Node { constructor(val, next = null) { this.val = val; this.next = next; }

printList(node) { let str = ''; let pointer = node; while (pointer != null) { str += pointer.val + ' => '; pointer = pointer.next; } console.log(str); } }

function reverseSub(head, p, q) { let beforeSub = null; let afterSub = null;

let pointer = head; let counter = 1; let start = null; let end = null;

//Save the nodes before and after the sublist, and the start and end of the sublist while (counter

Reading Progress

0%