Shift Linked List

Tags

Shift Linked List

Category

Linked Lists

Difficulty

Medium

Problem Statement

Given the head of a singly linked list and an integer k, shift the list by k positions. A positive k means shifting each node k positions forward (toward the tail), which effectively moves the last k nodes to the front. A negative k means shifting backward (the first |k| nodes move to the end). Return the head of the shifted list.

Intuition

Shifting a linked list by k positions is equivalent to finding the correct "cut point," detaching the list there, and reattaching the parts in reverse order. Since shifting by the length of the list results in the same list, we work with k modulo the list length to avoid unnecessary full rotations.

For a forward shift by k: the new head is the node at position (length - k) from the start, and the node just before it becomes the new tail.

Approach

  1. Calculate the length of the list and get a reference to the tail node.
  2. Compute the effective shift: k = k % length. If k is 0, return the original head.
  3. If k is negative, convert it to the equivalent positive shift: k = k + length.
  4. Find the new tail at position length - k - 1 from the head (0-indexed).
  5. The new head is newTail.next.
  6. Set newTail.next = null to terminate the first part.
  7. Set the original tail's next to the original head to connect the two parts.
  8. Return the new head.

Pseudocode

function shiftLinkedList(head, k):
    if head is null:
        return null

    length = 1
    tail = head
    while tail.next is not null:
        tail = tail.next
        length += 1

    k = k % length
    if k == 0:
        return head
    if k < 0:
        k = k + length

    newTail = head
    for i from 1 to (length - k - 1):
        newTail = newTail.next

    newHead = newTail.next
    newTail.next = null
    tail.next = head

    return newHead

Time & Space Complexity

  • Time: O(n), where n is the length of the list. We traverse the list twice: once to find the length and tail, once to find the cut point.
  • Space: O(1). Only a constant number of pointers are used.

Key Insights

  • Taking k modulo the list length handles cases where k is larger than the list length or negative.
  • A forward shift by k is the same as a backward shift by (length - k).
  • The operation is essentially making the list circular temporarily, then cutting it at the right point.
  • No nodes are created or destroyed; only pointer manipulations are needed.

Edge Cases

  • k = 0 or k is a multiple of the list length: return the original list unchanged.
  • k is negative: equivalent to shifting in the opposite direction.
  • |k| is greater than the list length: the modulo operation handles this.
  • Single-node list: any shift returns the same node.
  • k equals the list length: the list remains unchanged.

Linked mentions