3 Tips for Mastering Linked List Problems

As you solve linked list problems, you’ll begin to recognize common patterns that simplify approaching new linked list challenges. In this article, we’ll explore those patterns!

1. Slow and Fast pointers

This uses 2 pointers that move through the linked list at two different speeds. Let’s look at an example to better understand how this technique works.

If we want to get to the middle of the linked list, we can do this without the need to calculate the length of the linked list.

Demonstration of finding middle node

We move the slow pointer ‘s’ 1 step at a time and fast pointer ‘f’ 2 steps at a time. When the fast pointer reaches the end of the list (or the node before the end if the list has an even number of nodes), the slow pointer will be at the middle node of the list.

This technique can also be we used to solve:

1. Leetcode 141 Linked List Cycle- The slow pointer moves by 1 and fast pointer by 2. If there is a cycle in the linked list, the fast pointer will eventually meet the slow pointer.
2. Leetcode 19 Remove Nth Node From End of List- Move the fast pointer n steps ahead while the slow pointer remains at the beginning. Then, move both pointers one step at a time until the fast pointer reaches the end. The slow pointer will be at the node just before the one to be removed.
3. Leetcode 234 Palindrome Linked List- Use the slow and fast pointers to find the middle of the linked list, then reverse the second half and compare it with the first half.

2. Dummy node

A dummy node, also known as a sentinel node, does not contain real data and typically points to the head node of the linked list. It simplifies linked list operations and reduces the need for special cases in the code.

Let’s say we are given a linked list and we need to delete a node from a linked list.

Python snippets to demonstrate use of dummy node

Without a dummy node, we need to handle the deletion of the head node separately. While if we have a dummy node, no such special case is needed as the dummy node is pointing to the head node. The code with the dummy node is thus simplified and the logic stays consistent regardless of the node’s position in the linked list.

This technique can also be we used to solve:

1. Leetcode 707 Design Linked List
2. Leetcode 21 Merge Two Sorted Lists
3. Leetcode 2 Add Two Numbers represented by linked lists

3. Reversing a Linked List

Reversing a linked list might seem straightforward, but understanding how pointers manipulate the list structure can be challenging. Also, reversing a linked list frequently serves as a crucial subproblem in various linked list problems.

Python snippet for reversing a linked list

Here’s how the code works!

Demonstration of reversing a linked list

Step (1) initializes the prev and current pointers. Steps (2) through (5) reverse the linked list node by node. When current becomes NULL in Step (5), the reversal is complete, and the reversed linked list is in Step (6).

This is a subproblem in many linked list problems, such as:

1. Leetcode 234 Palindrome Linked List- Use the slow and fast pointers to find the middle of the linked list, then reverse the second half and compare it with the first half.
2. Leetcode 816 Double a Number Represented as a Linked List — First, reverse the list, then double the number, and finally reverse the list again to obtain the doubled number.
3. Leetcode143 Reorder List — Find the middle of the linked list, reverse the second half. Merge the first half and the reversed second half by alternating nodes from each half.

4. Bonus tip- Master the Fundamentals

As basic and obvious as it sounds, none of the above tips will be useful if the fundamentals of linked lists are not clear. Often, we ignore the basics before diving into more difficult problems (Been there, done that!). It’s crucial to understand how to create a linked list, insert, delete, swap elements, and traverse the list. One small mistake can render the entire solution incorrect. Mastering these basics is essential for solving ALL linked list problems.

A few problems to help you strengthen your basics:

1. Leetcode 707 Design Linked List
2. Leetcode 146 LRU cache
3. Leetcode 237 Delete Node in a Linked List
4. Leetcode 86 Partition List

Thanks for reading! Happy Coding!