Problems

Put your linked list knowledge into practice with these curated problems. Each problem demonstrates different aspects of pointer manipulation and algorithmic thinking. Refer to the Code Templates for standardized implementations.

Easy Problems

1. Merge Two Sorted Lists

Brief: Merge two sorted linked lists into one sorted list.
Why this pattern?: Requires pointer comparison and the dummy node pattern for building a new list.
Key Insight: Use a dummy node to simplify head handling, then iteratively compare and append the smaller node.

  graph LR
    subgraph List1 [List 1]
        L1[1] --> L2[3]
        L2 --> L3[5]
    end

    subgraph List2 [List 2]
        M1[2] --> M2[4]
        M2 --> M3[6]
    end

    subgraph Merged [Merged List]
        D[Dummy] --> R1[1]
        R1 --> R2[2]
        R2 --> R3[3]
        R3 --> R4[4]
        R4 --> R5[5]
        R5 --> R6[6]
    end

    style D fill:#ffd,stroke:#333
    style R1 fill:#aaf,stroke:#333
    style R2 fill:#aaf,stroke:#333
    style R3 fill:#aaf,stroke:#333

function mergeTwoLists(list1, list2) {
    const dummy = new ListNode(0);
    let tail = dummy;

    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    tail.next = list1 !== null ? list1 : list2;
    return dummy.next;
}

def merge_two_lists(list1, list2):
    dummy = ListNode(0)
    tail = dummy

    while list1 and list2:
        if list1.val < list2.val:
            tail.next = list1
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next

    tail.next = list1 or list2
    return dummy.next

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (list1 != null && list2 != null) {
        if (list1.val < list2.val) {
            tail.next = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            list2 = list2.next;
        }
        tail = tail.next;
    }

    tail.next = list1 != null ? list1 : list2;
    return dummy.next;
}

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;

    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    tail->next = list1 != nullptr ? list1 : list2;
    return dummy->next;
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }

    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

def merge_two_lists(list1, list2)
  dummy = ListNode.new(0)
  tail = dummy

  while list1 && list2
    if list1.val < list2.val
      tail.next = list1
      list1 = list1.next
    else
      tail.next = list2
      list2 = list2.next
    end
    tail = tail.next
  end

  tail.next = list1 || list2
  dummy.next
end

Medium Problems

2. Reverse Linked List

Brief: Reverse a singly linked list and return the new head.
Why this pattern?: Demonstrates the core three-pointer reversal technique used in many problems.
Key Insight: Save the next node before overwriting the pointer, then reverse and move all three pointers forward.

  graph LR
    subgraph Original [Original List]
        A[1] --> B[2]
        B --> C[3]
        C --> D[4]
    end

    subgraph Reversed [Reversed List]
        D[4] --> C[3]
        C --> B[2]
        B --> A[1]
    end

    style A fill:#aaf,stroke:#333
    style D fill:#aaf,stroke:#333

function reverseList(head) {
    let prev = null;
    let current = head;

    while (current !== null) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

def reverse_list(head):
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* current = head;

    while (current != nullptr) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head

    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    return prev
}

def reverse_list(head)
  prev = nil
  current = head

  while current
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
  end

  prev
end

3. Linked List Cycle

Brief: Determine if a linked list has a cycle.
Why this pattern?: Introduces Floyd’s cycle detection algorithm with fast and slow pointers.
Key Insight: If a cycle exists, the fast pointer (moving 2 steps) will eventually catch up to the slow pointer (moving 1 step).

  graph LR
    subgraph WithCycle [List with Cycle]
        A[1] --> B[2]
        B --> C[3]
        C --> D[4]
        D --> E[5]
        E --> C
    end

    style E fill:#f99,stroke:#333
    style C fill:#faa,stroke:#333,stroke-dasharray:5 5

function hasCycle(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) return true;
    }

    return false;
}

def has_cycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast) return true;
    }

    return false;
}

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) return true;
    }

    return false;
}

func hasCycle(head *ListNode) bool {
    slow, fast := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next

        if slow == fast {
            return true
        }
    }

    return false
}

def has_cycle(head)
  slow = fast = head

  while fast && fast.next
    slow = slow.next
    fast = fast.next.next

    return true if slow == fast
  end

  false
end

4. Palindrome Linked List

Brief: Check if a linked list is a palindrome.
Why this pattern?: Combines finding the middle, reversing, and comparing - three key linked list techniques.
Key Insight: Find the middle with slow/fast pointers, reverse the second half, then compare both halves.

  graph LR
    subgraph Original [Original List]
        A[1] --> B[2]
        B --> C[3]
        C --> D[2]
        D --> E[1]
    end

    subgraph Processed [After Processing]
        subgraph FirstHalf [First Half]
            A[1] --> B[2]
        end
        subgraph Reversed [Reversed Second Half]
            E[1] --> D[2]
        end
        FirstHalf -. compare .-> Reversed
    end

function isPalindrome(head) {
    if (head === null || head.next === null) return true;

    let slow = head;
    let fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let prev = null;
    let current = slow.next;
    slow.next = null;

    while (current !== null) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    let first = head;
    let second = prev;

    while (second !== null) {
        if (first.val !== second.val) return false;
        first = first.next;
        second = second.next;
    }

    return true;
}

def is_palindrome(head):
    if not head or not head.next:
        return True

    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    prev = None
    current = slow.next
    slow.next = None

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    first = head
    second = prev

    while second:
        if first.val != second.val:
            return False
        first = first.next
        second = second.next

    return True

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;

    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode prev = null;
    ListNode current = slow.next;
    slow.next = null;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    ListNode first = head;
    ListNode second = prev;

    while (second != null) {
        if (first.val != second.val) return false;
        first = first.next;
        second = second.next;
    }

    return true;
}

bool isPalindrome(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return true;

    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* prev = nullptr;
    ListNode* current = slow->next;
    slow->next = nullptr;

    while (current != nullptr) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    ListNode* first = head;
    ListNode* second = prev;

    while (second != nullptr) {
        if (first->val != second->val) return false;
        first = first->next;
        second = second->next;
    }

    return true;
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }

    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    var prev *ListNode
    current := slow.Next
    slow.Next = nil

    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    first, second := head, prev

    for second != nil {
        if first.Val != second.Val {
            return false
        }
        first = first.Next
        second = second.Next
    }

    return true
}

def is_palindrome(head)
  return true if !head || !head.next

  slow = fast = head
  while fast.next && fast.next.next
    slow = slow.next
    fast = fast.next.next
  end

  prev = nil
  current = slow.next
  slow.next = nil

  while current
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
  end

  first = head
  second = prev

  while second
    return false if first.val != second.val
    first = first.next
    second = second.next
  end

  true
end

5. Reorder List

Brief: Reorder list to interleave first and last nodes.
Why this pattern?: Combines finding middle, reversing, and merging - three key linked list operations.
Key Insight: Find the middle, reverse the second half, then merge the two halves alternately.

  graph LR
    subgraph Original [Original]
        A[L0] --> B[L1]
        B --> C[L2]
        C --> D[L3]
        D --> E[L4]
    end

    subgraph Reordered [Reordered]
        A[L0] --> E[L4]
        E --> B[L1]
        B --> D[L3]
        D --> C[L2]
    end

function reorderList(head) {
    if (head === null || head.next === null) return;

    let slow = head;
    let fast = head;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let prev = null;
    let current = slow.next;
    slow.next = null;

    while (current !== null) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    let first = head;
    let second = prev;

    while (second !== null) {
        const temp1 = first.next;
        const temp2 = second.next;

        first.next = second;
        second.next = temp1;

        first = temp1;
        second = temp2;
    }
}

def reorder_list(head):
    if not head or not head.next:
        return

    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    prev = None
    current = slow.next
    slow.next = None

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    first = head
    second = prev

    while second:
        temp1 = first.next
        temp2 = second.next

        first.next = second
        second.next = temp1

        first = temp1
        second = temp2

public void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode prev = null;
    ListNode current = slow.next;
    slow.next = null;

    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    ListNode first = head;
    ListNode second = prev;

    while (second != null) {
        ListNode temp1 = first.next;
        ListNode temp2 = second.next;

        first.next = second;
        second.next = temp1;

        first = temp1;
        second = temp2;
    }
}

void reorderList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return;

    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    ListNode* prev = nullptr;
    ListNode* current = slow->next;
    slow->next = nullptr;

    while (current != nullptr) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    ListNode* first = head;
    ListNode* second = prev;

    while (second != nullptr) {
        ListNode* temp1 = first->next;
        ListNode* temp2 = second->next;

        first->next = second;
        second->next = temp1;

        first = temp1;
        second = temp2;
    }
}

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    var prev *ListNode
    current := slow.Next
    slow.Next = nil

    for current != nil {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    first, second := head, prev

    for second != nil {
        temp1 := first.Next
        temp2 := second.Next

        first.Next = second
        second.Next = temp1

        first = temp1
        second = temp2
    }
}

def reorder_list(head)
  return if !head || !head.next

  slow = fast = head
  while fast.next && fast.next.next
    slow = slow.next
    fast = fast.next.next
  end

  prev = nil
  current = slow.next
  slow.next = nil

  while current
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
  end

  first = head
  second = prev

  while second
    temp1 = first.next
    temp2 = second.next

    first.next = second
    second.next = temp1

    first = temp1
    second = temp2
  end
end

Hard Problems

6. Reverse Nodes in k-Group

Brief: Reverse linked list nodes in groups of size k.
Why this pattern?: Combines the reversal template with group processing and boundary checks.
Key Insight: Use recursion or iteration to process k nodes at a time, checking if enough nodes exist before reversing.

  graph LR
    subgraph Original [Original List]
        A1[1] --> A2[2] --> A3[3]
        A3 --> B1[4] --> B2[5] --> B3[6]
        B3 --> C1[7]
    end

    subgraph Reversed [k=3 Reversed]
        subgraph Group1 [Group 1 Reversed]
            A3[3] --> A2[2]
            A2 --> A1[1]
        end
        subgraph Group2 [Group 2 Reversed]
            B3[6] --> B2[5]
            B2 --> B1[4]
        end
        subgraph Group3 [Group 3 &lt; k]
            C1[7]
        end
        Group1 --> Group2
        Group2 --> Group3
    end

function reverseKGroup(head, k) {
    let count = 0;
    let current = head;

    while (current !== null && count < k) {
        current = current.next;
        count++;
    }

    if (count < k) return head;

    let prev = null;
    current = head;

    for (let i = 0; i < k; i++) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    head.next = reverseKGroup(current, k);
    return prev;
}

def reverse_k_group(head, k):
    count = 0
    current = head

    while current and count < k:
        current = current.next
        count += 1

    if count < k:
        return head

    prev = None
    current = head

    for _ in range(k):
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    head.next = reverse_k_group(current, k)
    return prev

public ListNode reverseKGroup(ListNode head, int k) {
    int count = 0;
    ListNode current = head;

    while (current != null && count < k) {
        current = current.next;
        count++;
    }

    if (count < k) return head;

    ListNode prev = null;
    current = head;

    for (int i = 0; i < k; i++) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    head.next = reverseKGroup(current, k);
    return prev;
}

ListNode* reverseKGroup(ListNode* head, int k) {
    int count = 0;
    ListNode* current = head;

    while (current != nullptr && count < k) {
        current = current->next;
        count++;
    }

    if (count < k) return head;

    ListNode* prev = nullptr;
    current = head;

    for (int i = 0; i < k; i++) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    head->next = reverseKGroup(current, k);
    return prev;
}

func reverseKGroup(head *ListNode, k int) *ListNode {
    count := 0
    current := head

    for current != nil && count < k {
        current = current.Next
        count++
    }

    if count < k {
        return head
    }

    var prev *ListNode
    current = head

    for i := 0; i < k; i++ {
        next := current.Next
        current.Next = prev
        prev = current
        current = next
    }

    head.Next = reverseKGroup(current, k)
    return prev
}

def reverse_k_group(head, k)
  count = 0
  current = head

  while current && count < k
    current = current.next
    count += 1
  end

  return head if count < k

  prev = nil
  current = head

  k.times do
    next_node = current.next
    current.next = prev
    prev = current
    current = next_node
  end

  head.next = reverse_k_group(current, k)
  prev
end

Recommended Study Order

Start with Problem 1 (Merge Two Sorted Lists) to understand the dummy node pattern and basic pointer manipulation. This builds a solid foundation for all other problems.

Move to Problem 2 (Reverse Linked List) to master the core three-pointer reversal technique. This is one of the most frequently used patterns.

Then tackle Problem 3 (Linked List Cycle) to learn Floyd’s algorithm and the fast/slow pointer technique. This appears in many variations.

Apply these combined skills in Problem 4 (Palindrome Linked List) which uses finding middle, reversing, and comparing all together.

Finally, challenge yourself with Problem 5 (Reorder List) and Problem 6 (Reverse Nodes in k-Group) to integrate multiple techniques in a single solution.

Key Insight: Linked list problems test your understanding of pointers and memory management. Focus on proper null checks and maintaining list integrity during manipulations. Drawing diagrams for every step is crucial for avoiding pointer errors.