Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 2: Rotate a LinkedList

Problem Statement

Given the head of a Singly LinkedList and a number ‘k’, rotate the LinkedList to the right by ‘k’ nodes.

Constraints:

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9

Solution

Another way of defining the rotation is to take the sub-list of ‘k’ ending nodes of the LinkedList and connect them to the beginning. Other than that we have to do three more things:

  1. Connect the last node of the LinkedList to the head, because the list will have a different tail after the rotation. 2

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lucas

· 4 years ago

Here is what I came up with! O(N) and a bit more readable IMO. Fire away! Image

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 rotate(self, head, rotations):
    
    def get_moves():
      length = 0
      node = head
      while node:
        node = node.next
        length += 1
      remain = length - (rotations % length)
      return remain

    # get the number of moves
    moves = get_moves()

    # move the nodes based on the number of moves
    count = 1
    node = head 
    while count < moves:
      count += 1
      node = node.next

    # cut the linkedlist to 2 parts
    next_part = node.next
    node.next = None

    # move to the end of the second part
    node = next_part
    while node and node.next:
      node = node.next

    # link the 2 parts again
    if node:
Eric Imho Jang

Eric Imho Jang

· 2 years ago

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

class Solution:
  def rotate(self, head, rotations):
    if rotations == 0:
      return head
    

    # get length of linked list and get necessary rotation
    length = 0
    current, previous = head, None
    while current:
      length += 1
      current = current.next
    
    remainder = rotations % length

    if remainder == 0:
      return head
    
    newHeadIndex = length - remainder
    current = head
    i = 0
    newHead = None
    while current:
      next = current.next
      # find and break the link before newHeadNode  
      if i == newHeadIndex - 1:    
        current.next = None
      # store new head node
      elif i == newHeadIndex:
        newHead = curre
bivani2805

bivani2805

· 16 days ago

for _ in range(rotations):
      curr, prev = head, None
      while curr.next is not None:
        prev = curr
        curr = curr.next
      
      curr.next = head
      head = curr
      prev.next = None
    return head
# Worst case is O(n^2) this helps me understand the pattern more