Day 18: Linked List Interview Problems 🐍

1. Implement a Singly Linked List

Design a Singly Linked List class from scratch. It should support the fundamental operations: insertion, deletion, searching for a value, and traversing the list.

Examples

# Assume `ll` is an instance of your LinkedList class
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
ll.traverse()       # Output: 10 -> 20 -> 30

ll.search(20)       # Output: True
ll.delete_node(20)
ll.traverse()       # Output: 10 -> 30
ll.search(20)       # Output: False

Constraints & Edge Cases

Node Class: Start by defining a `Node` class with `data` and `next` attributes.
Edge Cases: Handle operations on an empty list, and when deleting the head or tail node.
Complexity: Analyze the time and space complexity for each implemented method.

2. Reverse a Linked List

Given the `head` of a singly linked list, reverse the list in-place and return the new head.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5 -> None
Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

Constraints & Edge Cases

Time Complexity: Aim for $O(n)$, where $n$ is the number of nodes.
Space Complexity: The iterative solution should be $O(1)$. A recursive solution is also possible but will use $O(n)$ space on the call stack.
Edge Cases: An empty list or a list with a single node.

3. Detect a Cycle in a Linked List

Given the `head` of a linked list, determine if it has a cycle. A cycle exists if some node in the list can be reached again by continuously following the `next` pointer.

Examples

Input:  head = 3 -> 2 -> 0 -> -4 -> (points back to 2)
Output: True

Input:  head = 1 -> 2 -> None
Output: False

Constraints & Edge Cases

Algorithm: This is a classic use case for Floyd's Tortoise and Hare (slow and fast pointers) algorithm.
Time Complexity: $O(n)$.
Space Complexity: $O(1)$.
Edge Cases: Empty list, single node list.

4. Merge Two Sorted Linked Lists

You are given the heads of two sorted linked lists, `list1` and `list2`. Merge them into a single, sorted linked list and return the head of the merged list.

Examples

Input:  list1 = 1 -> 2 -> 4, list2 = 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Constraints & Edge Cases

Time Complexity: $O(n + m)$, where $n$ and $m$ are the lengths of the two lists.
Space Complexity: $O(1)$ if you rearrange the existing nodes.
Edge Cases: Handle cases where one or both of the input lists are empty.

5. Remove N-th Node From End of List

Given the `head` of a linked list and an integer `n`, remove the $n$-th node from the end of the list and return its head.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5

Input:  head = 1, n = 1
Output: None (empty list)

Constraints & Edge Cases

Approach: A one-pass solution is preferred, typically using two pointers.
Time Complexity: $O(L)$, where $L$ is the list length.
Space Complexity: $O(1)$.
Edge Cases: What if `n` is equal to the length of the list (i.e., you need to remove the head)? A dummy node can simplify this.

6. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order. Add the two numbers and return the sum as a new linked list.

Examples

Input:  l1 = 2 -> 4 -> 3, l2 = 5 -> 6 -> 4
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Constraints & Edge Cases

Carry-over: Remember to handle the carry when the sum of digits exceeds 9.
List Lengths: The lists can be of different lengths.
Time Complexity: $O(\max(n, m))$.
Space Complexity: $O(\max(n, m))$ for the result list.

7. Palindrome Linked List

Given the `head` of a singly linked list, return `true` if it is a palindrome and `false` otherwise.

Examples

Input:  1 -> 2 -> 2 -> 1
Output: True

Input:  1 -> 2
Output: False

Constraints & Edge Cases

Optimal Solution: An efficient solution involves finding the middle of the list, reversing the second half, and then comparing the two halves.
Time Complexity: $O(n)$.
Space Complexity: $O(1)$.
Post-check: Remember to restore the list to its original state if required by the interviewer.

8. Intersection Node of Two Linked Lists

Given the heads of two singly linked-lists `headA` and `headB`, return the node at which the two lists intersect. If they do not intersect, return `null`.

Examples

# listA = 4 -> 1 -> 8 -> 4 -> 5
# listB = 5 -> 6 -> 1 -> 8 -> 4 -> 5
# The lists intersect at the node with value 1.
Output: Reference to the node with value 1

Constraints & Edge Cases

Core Idea: The problem is that the lists can have different lengths before the intersection point. Find a way to make the pointers travel the same total distance.
Time Complexity: $O(n + m)$.
Space Complexity: $O(1)$.

9. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of the list `k` at a time and return the modified list. `k` is a positive integer and is less than or equal to the length of the list.

Examples

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 2 -> 1 -> 4 -> 3 -> 5

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5

Constraints & Edge Cases

Final Group: If the number of remaining nodes is less than `k`, they should be left as they are.
Complexity: This is a challenging problem. Aim for $O(n)$ time and $O(1)$ space. Recursion can simplify the logic but may use $O(n/k)$ stack space.

10. Copy List with Random Pointer

Construct a deep copy of a linked list where each node contains a `val`, a `next` pointer, and an additional `random` pointer which can point to any node in the list or `null`.

Examples

# The input is a list of nodes where each node is represented as [val, random_index].
Input:  head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Constraints & Edge Cases

Deep Copy: The copied list should be made of new nodes, not references to the old ones.
Common Approach: Use a hash map to store a mapping from old nodes to new nodes. This takes $O(n)$ time and $O(n)$ space.
Optimal Approach: A clever $O(1)$ space solution exists where you weave the new nodes into the original list, connect the random pointers, and then separate the lists.

Note from Your Interviewer 📝

Draw it Out: Always use a whiteboard or paper to draw the nodes and trace how your pointers (`head`, `current`, `prev`, `next`, `slow`, `fast`) are moving. This prevents a huge number of bugs.
Handle Nulls: Before you access `node.next`, always ask yourself: "What if `node` is `None`?" This is the most common source of errors.
Use a Dummy Head: For problems involving list modification (like removing the head or merging), creating a `dummy` or `sentinel` node before the actual head can unify your logic and eliminate many edge cases.
Communicate Your Approach: Talk through your logic before and while you code. Explain the trade-offs of your chosen approach (e.g., iterative vs. recursive, time vs. space).