Master linked list manipulation techniques including reversing, merging, cycle detection, and pointer arithmetic. These fundamental patterns appear in countless interview problems and real-world systems.
Linked lists are foundational data structures requiring careful pointer manipulation. Master the core patterns and you'll handle even the trickiest list problems with confidence.
All linked list problems in C# work with the standard ListNode definition:
public class ListNode { public int val; public ListNode next; public ListNode(int val = 0, ListNode next = null) { this.val = val; this.next = next; } }
Singly: Each node has a next pointer only. Efficient forward traversal, harder backward.
Doubly: Each node has next and prev pointers. Bidirectional traversal, but more memory.
Most interview problems use singly linked lists unless explicitly stated.
A dummy node pointing to the head simplifies edge cases (removing first node, merging lists):
// Create dummy node to unify edge cases ListNode dummy = new ListNode(0); dummy.next = head; ListNode current = dummy; // Now you can safely modify head without special cases while (current.next != null) { // Process and potentially modify head current = current.next; } return dummy.next; // Always return through dummy
Two pointers moving at different speeds detect cycles and find middle nodes:
// Detect cycle: slow moves 1 step, fast moves 2 steps ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // Cycle detected return true; } } return false;
Iterative approach (3-pointer): Maintain prev, current, next to reverse in-place.
public ListNode ReverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode nextTemp = current.next; // Save next current.next = prev; // Reverse link prev = current; // Move prev forward current = nextTemp; // Move current forward } return prev; // New head }
To find and manipulate nodes N steps from end, use two pointers with a fixed gap:
// Set up pointers N steps apart ListNode first = head, second = head; for (int i = 0; i < N; i++) { if (first == null) return null; first = first.next; } // Move both until first reaches end while (first != null) { first = first.next; second = second.next; } // Now second is at desired position
Reverse a singly linked list. You may do it iteratively or recursively. The iterative approach is preferred for interviews.
prev (null), current (head), nextTemppublic class Solution { public ListNode ReverseList(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { // 1. Save next node ListNode nextTemp = current.next; // 2. Reverse the link current.next = prev; // 3. Move pointers forward prev = current; current = nextTemp; } // prev is now the new head return prev; } }
| Step | prev | current | nextTemp | Action |
|---|---|---|---|---|
| 0 | null | 1 | — | Initialize |
| 1 | 1 | 2 | 2 | 1.next = null |
| 2 | 2 | 3 | 3 | 2.next = 1 |
| 3 | 3 | null | null | 3.next = 2, return 3 |
You are given the heads of two sorted linked lists list1 and list2. Merge them into one sorted list.
public class Solution { public ListNode MergeTwoLists(ListNode list1, ListNode list2) { // Dummy node eliminates edge case for head assignment ListNode dummy = new ListNode(0); ListNode current = dummy; // Compare and merge while both lists have nodes while (list1 != null && list2 != null) { if (list1.val <= list2.val) { current.next = list1; list1 = list1.next; } else { current.next = list2; list2 = list2.next; } current = current.next; } // Append remaining nodes (one list will be null) if (list1 != null) { current.next = list1; } else { current.next = list2; } return dummy.next; } }
| Step | list1 | list2 | Comparison | Appended |
|---|---|---|---|---|
| 1 | 1 | 1 | equal | list1: 1 |
| 2 | 2 | 1 | list2 < list1 | list2: 1 |
| 3 | 2 | 3 | list1 < list2 | list1: 2 |
| 4 | 4 | 3 | list2 < list1 | list2: 3 |
| 5 | 4 | 4 | equal | list1: 4 |
| 6 | null | 4 | — | Append list2: 4 |
Given the head of a linked list, determine if the list has a cycle in it. A cycle exists if a node's next pointer eventually points back to a node already visited.
public class Solution { public bool HasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; // Move slow 1 step, fast 2 steps while (fast != null && fast.next != null) { slow = slow.next; // 1 step fast = fast.next.next; // 2 steps // If they meet, there's a cycle if (slow == fast) { return true; } } // If we reach here, no cycle return false; } }
If a cycle exists with length C and the distance from head to cycle start is D:
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
public class Solution { public ListNode DetectCycleStart(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; // Phase 1: Detect cycle while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // Cycle detected break; } } // No cycle if (fast == null || fast.next == null) { return null; } // Phase 2: Find cycle start // Move one pointer to head slow = head; // Move both one step at a time while (slow != fast) { slow = slow.next; fast = fast.next; } // They meet at cycle start return slow; } }
Let D = distance from head to cycle start, C = cycle length, when they meet at point x (x steps into cycle):
Given the head of a linked list, remove the Nth node from the end of the list and return the head.
public class Solution { public ListNode RemoveNthFromEnd(ListNode head, int n) { // Dummy helps when removing head ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Move first pointer n+1 steps ahead for (int i = 0; i <= n; i++) { if (first == null) { return head; // n is larger than list } first = first.next; } // Move both pointers until first reaches end while (first != null) { first = first.next; second = second.next; } // Remove the nth node second.next = second.next.next; return dummy.next; } }
| Phase | Action | first | second |
|---|---|---|---|
| Setup | i=0 | dummy → 1 | dummy |
| i=1 | 1 → 2 | dummy | |
| i=2 | 2 → 3 | dummy | |
| i=3 | null | dummy | |
| Move Both | Iteration 1 | null | 1 |
| Iteration 2 | null | 2 | |
| Iteration 3 | null | 3 | |
| Remove | 3.next = 5 | — | — |
Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one.
public class Solution { public ListNode MiddleNode(ListNode head) { ListNode slow = head; ListNode fast = head; // Fast moves 2 steps, slow moves 1 step while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // When fast reaches end, slow is at middle return slow; } }
| Iteration | slow | fast | fast.next |
|---|---|---|---|
| 0 | 1 | 1 | 2 |
| 1 | 2 | 3 | 4 |
| 2 | 3 | 5 | null |
| 3 | 3 (return) | null | — |
For [1, 2, 3, 4]: Returns node 3 (second middle), not node 2. This is because fast.next becomes null before fast itself.
Given the head of a singly linked list, return true if it is a palindrome, or false otherwise.
public class Solution { public bool IsPalindrome(ListNode head) { // Step 1: Find middle ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // Step 2: Reverse second half ListNode reversedHalf = Reverse(slow); // Step 3: Compare first half and reversed second half ListNode left = head; ListNode right = reversedHalf; while (right != null) { if (left.val != right.val) { return false; } left = left.next; right = right.next; } return true; } private ListNode Reverse(ListNode head) { ListNode prev = null; ListNode current = head; while (current != null) { ListNode next = current.next; current.next = prev; prev = current; current = next; } return prev; } }
| Step | Description | Result |
|---|---|---|
| 1 | Find middle with fast/slow | slow at node 2 (second) |
| 2 | Reverse from middle | 1←2←2→1, second half: 1→2 |
| 3 | Compare: 1==1, 2==2 | true |
Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If lists don't intersect, return null.
public class Solution { public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; // Move both pointers, swap to other list when reaching end while (pA != pB) { // Move to next or redirect to other list's head pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; // Meeting point (or both null if no intersection) } }
If lists have lengths m and n with intersection distance k from ends:
| Iteration | pA | pB | Action |
|---|---|---|---|
| 0 | 4 | 5 | Both advance |
| 1 | 1 | 6 | Both advance |
| 2 | 8 | 1 | Both advance |
| 3 | 4 | 8 | Both advance |
| 4 | 5 | 4 | Both advance |
| 5 | null→5 | 5 | pA swaps to B |
| 6 | 8 (meet) | null→4 | pB swaps to A |
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a linked list.
public class Solution { public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode current = dummy; int carry = 0; // Process both lists and carry while (l1 != null || l2 != null || carry != 0) { // Get current digits or 0 if list is exhausted int val1 = l1 != null ? l1.val : 0; int val2 = l2 != null ? l2.val : 0; // Sum and separate digit from carry int sum = val1 + val2 + carry; int digit = sum % 10; carry = sum / 10; // Append new node to result current.next = new ListNode(digit); current = current.next; // Move to next nodes l1 = l1 != null ? l1.next : null; l2 = l2 != null ? l2.next : null; } return dummy.next; } }
| Iter | l1 | l2 | sum | digit | carry |
|---|---|---|---|---|---|
| 1 | 2 | 5 | 7 | 7 | 0 |
| 2 | 4 | 6 | 10 | 0 | 1 |
| 3 | 3 | 4 | 8 | 8 | 0 |
carry != 0 handles this.You are given an array of K linked lists lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.
public class Solution { public ListNode MergeKLists(ListNode[] lists) { // Min-heap using PriorityQueue (C# 10+) // Comparer: node with smaller value has higher priority var pq = new PriorityQueue<ListNode, int>(); // Add all heads to heap foreach (var list in lists) { if (list != null) { pq.Enqueue(list, list.val); } } ListNode dummy = new ListNode(0); ListNode current = dummy; // Merge by always taking minimum while (pq.Count > 0) { ListNode minNode = pq.Dequeue(); current.next = minNode; current = current.next; // Add next node from same list to heap if (minNode.next != null) { pq.Enqueue(minNode.next, minNode.next.val); } } return dummy.next; } }
| Step | Heap Contents | Dequeue | Enqueue |
|---|---|---|---|
| Init | [1, 1, 2] | — | — |
| 1 | [1, 2] | 1 (list 1) | 4 |
| 2 | [2, 4] | 1 (list 2) | 3 |
| 3 | [2, 3, 4] | 2 (list 3) | 6 |
| 4 | [3, 4, 6] | 3 | 4 |
| 5 | [4, 4, 6] | 4 | 5 |
| 6 | [4, 5, 6] | 4 | — |
| 7 | [5, 6] | 5 | — |
| 8 | [6] | 6 | — |
Recursively merge pairs of lists, reducing K lists to 1 in log(K) rounds. Time: O(N log K) vs PriorityQueue O(N log K) but better constant factors for small K.
Where N = total nodes across all lists, K = number of lists