A LinkedList is a linear data structure consisting of a sequence of elements, called nodes, where each node contains two parts: data (the value or payload) and a reference (or link) to the next node in the sequence.
Unlike arrays, linked lists do not store elements in contiguous memory locations; instead, nodes are connected through pointers, allowing dynamic memory allocation and flexible insertion and deletion operations.
Key Components
Node: The basic unit of a linked list, containing:
| Operation | Linked List | Array |
|---|---|---|
| Access by index | ✖ O(n) | ✔ O(1) |
| Insert/delete at start | ✔ O(1) | ✖ O(n) |
| Insert/delete at end | ✔ O(1) | ✖ O(n) worst |
| Insert/delete in middle | ✔ O(1) | ✖ O(n) |
| Dynamic resizing | ✔ Native | ✖ May require copy/resize |
| Memory locality (cache) | ✖ Poor | ✔ Excellent |
1. Design and implement a Singly Linked List that supports the following operations:
If the list is empty, return "Null"
2. You are given the head of a singly linked list. Implement an efficient in-place algorithm to reverse the linked list. Return the new head of the reversed list.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | A list with 1 node: 1 → null | A long list with 10,000+ nodes | A null list (head = null) |
| Output | 1 → null (no change) | Full list reversed (last becomes head) | null |
| Explanation | No re-linking needed | Each node’s next pointer is reassigned | Edge condition, must handle gracefully |
3. You are given the head node of a singly linked list. Design an algorithm that return the total number of nodes.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | head → null (empty list) | Long list: head → 1 → 2 → ... → n → null | Single node: head → 42 → null |
| Output | 0 | n (number of nodes) | 1 |
| Explanation | No nodes, count is zero | Must traverse all nodes to count them | Only one node, count is one |
In singly linked lists, a loop occurs when a node's next pointer points to a previously visited node in the same list, rather than null. This creates a cyclic reference, leading to an infinite traversal unless handled correctly.
In industrial systems, detecting and managing such cycles is critical to avoid infinite loops, memory leaks, and application crashes, particularly in real-time systems, garbage collectors, and networked data structures.
4. You are given the head node of a singly linked list. Design an algorithm that returns true if there is a cycle in the linked list. Otherwise, return false.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | 1 → 2 → 3 → null | 1 → 2 → 3 → 4 → 5 → 6 → 3 (cycle starts at node 3) | null (empty list) |
| Output | false | true | false |
| Explanation | No cycle: traversal ends at null | Cycle detected when fast and slow meet at node 5 | No nodes exist; list is empty |
5. Design an algorithms that takes the head of a singly linked list and returns the middle element.
If the linked list has an odd number of nodes, return the exact middle node.
If the list has an even number of nodes, return the second of the two middle nodes.
The returned node should be the actual node object, not just its value.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | A 1-node list: [7] | A large even-length list: [1 → 2 → 3 → ... → 998 → 999 → 1000] | A 2-node list: [10 → 20] |
| Output | Node with value 7 | Node with value 501 | Node with value 20 |
| Explanation | Single node is trivially the middle. | Length is 1000 (even), so middle nodes are 500 and 501 → return 501. | 2 nodes → middle are 10 and 20 → return second (20). |
6. Given the head of a singly linked list and an integer key, Design an algorithm that delete the first occurrence of the node that has this key.
The list should be modified in-place and the updated head must be returned.
If the node with the given key does not exist, return the original head unchanged.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | head = [10, 20, 30], key = 10 | head = [10, 20, 30, 40, 50], key = 50 | head = [10], key = 15 |
| Output | [20, 30] | [10, 20, 30, 40] | [10] (unchanged) |
| Explanation | Key found at the head. Head is updated. | Key found at the last node. Full traversal. | Key not found. No deletion occurs. |
7. Given the head of a singly linked list, an integer position, and an integer value, write a function to insert a new node with the specified value at the given position.
If position is 0, insert the node at the beginning of the list.
If position is equal to the current length of the list, insert the node at the end.
If position is less than 0 or greater than the length of the list, do not perform the insertion, and return the original list.
The function should return the updated head of the list.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | head = [1, 2, 3], value = 0, pos = 0 | head = [1, 2, 3], value = 4, pos = 3 | value = 4, pos = 3 head = [1, 2, 3], value = 5, pos = 5 |
| Output | [20, 30] | [1, 2, 3, 4] | [1, 2, 3] (unchanged) |
| Explanation | [0, 1, 2, 3] | Insert at end (position = length) | Invalid position (pos > length), ignore op |
8. You are given the heads of two non-empty, sorted singly linked lists list1 and list2.
Design an algorithm that merges the two lists into a single, sorted linked list. The resulting list must be built by reusing and relinking the nodes from the original lists — do not allocate new nodes.
Return the head of the merged, sorted linked list.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | list1 = null list2 = 1 → 2 → 3 | list2 = 1 → 2 → 3 list1 = 1 → 3 → 5 list2 = 2 → 4 → 6 | list1 = 2 → 2 → 2 list2 = 2 → 2 |
| Output | 1 → 2 → 3 | 1 → 2 → 3 → 4 → 5 → 6 | 2 → 2 → 2 → 2 → 2 |
| Explanation | One list is null, so we return the other as-is | Alternating values force comparisons at every step | All values are equal; merge order determined by input |
9. Design an algorithm that takes a singly linked list and performs an in-place swap of every two neighboring nodes. The function should return the new head of the modified list.
The swapping should be done by re-linking the nodes — do not modify the node values.
If the list has an odd number of nodes, leave the last node as is.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | 1 -> 2 -> Null | 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> ... -> n -> Null | Null, 1 -> Null, 1 -> 2 -> 3 -> Null |
| Output | 2 -> 1 -> Null | All adjacent pairs are swapped, e.g., 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> ... | Null, 1 -> Null, 2 -> 1 -> 3 -> Null |
| Explanation | Only one pair exists, directly swapped. | Every node has a pair, all get swapped sequentially by updating .next | Handles empty list, single-node list, and last node unpaired (odd length) |
1. You are given the head of a singly linked list. Design an algorithm that detects whether a loop exists and remove the loop in-place by modifying the next pointer of the last node in the cycle so that it points to null.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | 1 → 2 → 3 → null | 1 → 2 → 3 → ... → 9999 → 10000 → 9999 | 1 → 2 → 3 → 4 → (back to 1) |
| Output | 1 → 2 → 3 → null | 1 → 2 → 3 → ... → 9999 → 10000 → null | 1 → 2 → 3 → 4 → null |
| Explanation | No loop exists; return as-is. | Loop is at the end; takes longest to detect and remove. | Loop starts from head; early detection needed and fixed correctly. |
2. You are given the heads of two non-empty singly linked lists. The lists may intersect at some node, forming a shared tail.
Design an algorithm that identifies the node where the intersection begins, if the two linked lists do not intersect, return null.
The lists must retain their original structure after the function returns.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | headA = A1 → A2 → C1 → C2 headB = B1 → C1 → C2 | headA = A1 → A2 → A3 → A4 → A5 headB = B1 → B2 → B3 → B4 → B5 | headA = null, headB = B1 → B2 OR headA = A1 → A2, headB = null |
| Output | Reference to node C1 | null | null |
| Explanation | The lists intersect starting at node C1. The shared tail C1 → C2 is common to both. | The lists do not intersect at all. All nodes are unique in memory. | One or both lists are null. Hence, no intersection is possible. |
3. You are given the head of a singly linked list and an integer k. Design an algorithm to reversethe list in group of k nodes.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input Parameters | Linked List: 1→2→3→4, k = 2 | Linked List: 1→2→3→4→5→6→7, k = 3 | Linked List: 1→2→3→4→5, k = 10 |
| Output | 2→1→4→3 | 3→2→1→6→5→4→7 | 1→2→3→4→5 (no changes) |
| Explanation | Two groups of size 2 reversed individually. | Two full groups (3 nodes each) reversed, last node left alone | No group of size 10 exists; hence, the list remains the same |
4. You are given two non-empty singly linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit.
Design the algorithm that add the two numbers and return the sum as a new linked list, also in reversed order.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | l1 = [0], l2 = [0] | l1 = [9,9,9,9,9], l2 = [9,9,9,9,9] | One list is shorter: l1 = [2,4,3], l2 = [5,6] |
| Output | [0] | [8,9,9,9,9,1] | [7,0,4] |
| Explanation | Sum is 0, so result is a single node | Full carry-over, extra node added at the end due to carry | Shorter list padded logically with 0s internally |
5. Given the head of a singly linked list and an integer k.
Design an algorithm that rotates the list to the right by k places. and return the new head of the rotated list.
The structure of the original list must be modified in-place.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | head = [1, 2, 3], k = 0 | head = [1, 2, 3, 4, 5], k = 3 | head = [1], k = 100 |
| Output | [1, 2, 3] | [3, 4, 5, 1, 2] | [1] |
| Explanation | No rotation needed when k = 0, original list is returned | k = 8 → effective k = 3, rotate right by 3 → last 3 nodes move to front | Single-node list remains unchanged regardless of k |
6. You are given a linked list where each node has :
Design an algorithm that creates a deep copy of the entire list such that:
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | 1 → 2 → 3 (randoms all null) | 1 → 2 → 3 → 4 → ... → N (randoms point randomly) | Empty list (null) |
| Output | Deep copy: 1′ → 2′ → 3′ (randoms all null) | Deep copy: All N nodes copied, next and random preserved | null |
| Explanation | Minimal logic: no random pointers to track | Maximum logic: Need to copy complex random structure without sharing references | No nodes to copy, return null |
7. Given a singly linked list where each node contains an integer. Design an algorithm that performs in-place sorting in ascending order and returns the head of the linked list.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | 1 -> 2 -> 3 -> 4 -> null | 4 -> 3 -> 2 -> 1 -> null | null (empty list) or 1 -> null |
| Output | 1 -> 2 -> 3 -> 4 -> null | 1 -> 2 -> 3 -> 4 -> null | null or 1 -> null |
| Explanation | List is already sorted; minimal work. | List is reverse sorted; full reordering needed (max comparisons/swaps). | Either no element or only one element; already sorted. |
8. Given a multilevel linked list where each node contains two pointers:
Design an in-place algorithm that flatten the multilevel list into a single-level singly linked list. The flattened list should:
Return the head of the flattened list.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | A flat list with no child pointers | A list where every node has a child, forming a deep nested structure | Empty list or single-node list |
| Output | Same list unchanged | Fully flattened list in depth-first order | null or single node |
| Explanation | No flattening needed since no child exists | All child nodes are recursively inserted after parents. Deep recursion or stack usage applies. | Minimal input, must handle safely without errors. |
9. Given the head of a singly linked list and an integer n. Design an algorithm that removes the nth node (1-based indexing) from the end of the list and return its head.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | List: 1 → 2 → 3, n = 1 | List: 1 → 2 → 3 → 4 → 5, n = 5 | List: 1, n = 1 |
| Output | 1 → 2 | 2 → 3 → 4 → 5 | null |
| Explanation | Last node (3rd from start) is removed in one pass | 5th from end = head, so head is removed | Only one node, and it's removed, resulting in empty list |
10. Given a singly linked list of integers. Design an algorithm that checks whether it forms a palindrome.
Return true if it is a palindrome, otherwise return false.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | 1 → 1 → 1 → 1 | 1 → 2 → 3 → 2 → 1 | 1 node (e.g., 1), or 2 different nodes (e.g., 1 → 2) |
| Output | true | true | true for 1 node, false for non-palindrome |
| Explanation | All values are the same. Easy match. | Requires full traversal and second-half reversal and comparison. | Edge case of minimal length. Algorithm must handle it gracefully without errors. |