Interview Bootcamp

0% completed

​

Solution: Reverse every K-element Sub-list

Problem Statement

Given the head of a LinkedList and a number ‘k’, reverse every ‘k’ sized sub-list starting from the head.

If, in the end, you are left with a sub-list with less than ‘k’ elements, reverse it too.

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Solution

The problem follows the In-place Reversal of a LinkedList pattern and is quite similar to Reverse a Sub-list. The only difference is that we have to reverse all the sub-lists. We can use the same approach, starting with the first sub-list (i.e.

.....

.....

.....

Like the course? Get enrolled and start learning!
D

Donald

· 4 years ago

How would you change the code if you have the remaining sublist values shouldn't be changed? ie. instead of 8 -> 7 you leave it at 7 -> 8

Show 4 replies
Renat Zamaletdinov

Renat Zamaletdinov

· 2 years ago

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

class Solution:
  def reverse(self, head, k):
    if k == 1:
      return head

    def sub_reverse(s, e):
      prev = None
      curr = s

      while curr != e:
        next_ = curr.next
        curr.next = prev
        prev = curr
        curr = next_

      return prev, start

    current = dummy = Node(-1, head)
    start = end = head

    while end:
      count = 0
      
      while end and count < k:
        end = end.next
        count += 1

      new_start, new_end = sub_reverse(start, end if count == k else None)

      current.next = new_start
      current = new_end
      start = end

    return dummy.next
L

Lucas

· 4 years ago

Here is my solution! LMK if you break it LOL Image

S

Shan

· 4 years ago

This solution breaks for

[1,2,3,4,5] 3

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def reverse(self, head, k):
    node = head
    new_head = None
    prev_end = None

    # while we still have remaining parts.
    while node:
      end = node
      prev = None
      count = 0

      # reverse the part.
      while node and count < k:
        count += 1
        next_node = node.next
        node.next = prev 
        prev = node 
        node = next_node
      begin = prev 

      # link the previous part end to the begin of the new part.
      if prev_end:
        prev_end.next = begin
      prev_end = end

      # set the new head of Linkedlist. it points to the first part begin.
      if not new_head:
        new_head = begin

      count = 0
    
    # We have to do this to prevent the Linkedlist from having circular loop at the end.