Introduction
Linked lists are fundamental data structures that every programmer should master. Unlike arrays, linked lists offer dynamic memory allocation and efficient insertions/deletions, making them essential for building scalable applications.
In this comprehensive guide, we’ll explore linked list concepts through practical problems and clean, production-ready code examples in both C# and Python.
What is a Linked List?
A linked list is a linear data structure where elements are stored in nodes. Each node contains:
- Data: The value stored in the node
- Next pointer: Reference to the next node in the sequence
Unlike arrays, linked list elements aren’t stored in contiguous memory locations, allowing for efficient insertions and deletions.
Types of Linked Lists
- Singly Linked List: Each node points to the next node
- Doubly Linked List: Each node has pointers to both next and previous nodes
- Circular Linked List: The last node points back to the first node
Problem 1: Linked List Cycle Detection
Difficulty: Easy
Tags: Two Pointers, Fast & Slow Pointers
Problem Statement
Given the head of a linked list, determine if it contains a cycle. A cycle exists when a node can be reached again by following the next pointers.
Approach: Floyd’s Cycle Detection (Tortoise and Hare)
This elegant algorithm uses two pointers moving at different speeds:
- Slow pointer: Moves one step at a time
- Fast pointer: Moves two steps at a time
If there’s a cycle, the fast pointer will eventually meet the slow pointer. If there’s no cycle, the fast pointer reaches the end.
C# Solution
public class Solution
{
public bool HasCycle(ListNode head)
{
if (head == null) return false;
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;
}
}
Python Solution
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head:
return False
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Time Complexity: O(n)
Space Complexity: O(1)
Problem 2: Linked List Cycle II – Find the Cycle Start
Difficulty: Medium
Tags: Two Pointers, Mathematical Proof
Problem Statement
Given a linked list, return the node where the cycle begins. If there’s no cycle, return null.
Mathematical Insight
When the slow and fast pointers meet:
- Distance traveled by slow: a + b
- Distance traveled by fast: a + 2b + c
Since fast moves twice as fast: 2(a + b) = a + 2b + c
Simplifying: a = c
This means the distance from the head to the cycle start equals the distance from the meeting point to the cycle start!
C# Solution
public class Solution
{
public ListNode DetectCycle(ListNode head)
{
if (head == null) return null;
ListNode slow = head;
ListNode fast = head;
// Phase 1: Detect if cycle exists
while (fast != null && fast.next != null)
{
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
{
// Phase 2: Find cycle start
slow = head;
while (slow != fast)
{
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
Python Solution
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return None
slow = head
fast = head
# Phase 1: Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Phase 2: Find cycle start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None
Time Complexity: O(n)
Space Complexity: O(1)
Problem 3: Remove Duplicates from Sorted List
Difficulty: Easy
Tags: Linked List Traversal
Problem Statement
Given a sorted linked list, delete all duplicates so that each element appears only once.
Approach
Traverse the list and compare each node with its next node. If values match, skip the duplicate by updating the next pointer.
C# Solution
public class Solution
{
public ListNode DeleteDuplicates(ListNode head)
{
ListNode current = head;
while (current != null && current.next != null)
{
if (current.val == current.next.val)
{
current.next = current.next.next;
}
else
{
current = current.next;
}
}
return head;
}
}
Python Solution
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
current = head
while current and current.next:
if current.val == current.next.val:
current.next = current.next.next
else:
current = current.next
return head
Time Complexity: O(n)
Space Complexity: O(1)
Problem 4: Remove Duplicates from Sorted List II
Difficulty: Medium
Tags: Sentinel Node, Two Pointers
Problem Statement
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers.
Approach: Sentinel Node Pattern
Use a sentinel (dummy) node to handle edge cases elegantly. This allows uniform handling of head deletions.
C# Solution
public class Solution
{
public ListNode DeleteDuplicates(ListNode head)
{
ListNode sentinel = new ListNode(0, head);
ListNode predecessor = sentinel;
while (head != null)
{
if (head.next != null && head.val == head.next.val)
{
// Skip all duplicates
while (head.next != null && head.val == head.next.val)
{
head = head.next;
}
predecessor.next = head.next;
}
else
{
predecessor = predecessor.next;
}
head = head.next;
}
return sentinel.next;
}
}
Python Solution
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
sentinel = ListNode(0, head)
predecessor = sentinel
while head:
if head.next and head.val == head.next.val:
# Skip all duplicates
while head.next and head.val == head.next.val:
head = head.next
predecessor.next = head.next
else:
predecessor = predecessor.next
head = head.next
return sentinel.next
Time Complexity: O(n)
Space Complexity: O(1)
Problem 5: Add Two Numbers
Difficulty: Medium
Tags: Math, Carry Logic
Problem Statement
You are given two non-empty linked lists representing two non-negative integers stored in reverse order. Add the two numbers and return the sum as a linked list.
Example
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807
Approach
Simulate addition with carry, just like adding numbers by hand. Handle different list lengths gracefully.
C# Solution
public class Solution
{
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
ListNode sentinel = new ListNode(0);
ListNode current = sentinel;
int carry = 0;
while (l1 != null || l2 != null || carry > 0)
{
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
current.next = new ListNode(sum % 10);
current = current.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return sentinel.next;
}
}
Python Solution
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
sentinel = ListNode(0)
current = sentinel
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return sentinel.next
Time Complexity: O(max(m, n)) where m and n are list lengths
Space Complexity: O(max(m, n)) for the result list
Key Takeaways
Common Patterns
- Two Pointers: Essential for cycle detection and finding middle elements
- Sentinel/Dummy Node: Simplifies edge cases, especially for head deletions
- In-place Modification: Many linked list problems can be solved without extra space
Best Practices
- Always check for null before accessing
next - Use sentinel nodes to avoid special-casing the head
- Name variables clearly (
slow/fastinstead ofp1/p2) - Add complexity analysis comments
When to Use Linked Lists
Advantages:
- Dynamic size
- Efficient insertions/deletions (O(1) with pointer)
- No wasted memory
Disadvantages:
- No random access (O(n) lookup)
- Extra memory for pointers
- Poor cache locality
Practice Problems
Ready to test your skills? Try these related problems:
- Reverse Linked List – Classic reversal pattern
- Merge Two Sorted Lists – Practice with multiple pointers
- Palindrome Linked List – Combine multiple techniques
- Intersection of Two Linked Lists – Advanced two-pointer technique
- Remove Nth Node From End – Two-pointer with gap
Conclusion
Linked lists are more than just interview questions—they’re the foundation for understanding pointers, memory management, and data structure design. Master these patterns, and you’ll be well-equipped to tackle complex algorithms.
What’s Next? In our next article, we’ll explore advanced linked list techniques including reversal, merging, and partitioning.
Happy coding! 🚀
Have questions or suggestions? Drop a comment below!
