Linked List
Linked List Overview
Count: 10
This page covers common operations and strategies that frequently show up in linked list problems for the coding interview.
Basics
A linked list is a data structure consisting of sequence of a nodes, where each node contains a value and reference to the next node in the sequence.
In Python, we can represent a linked list node with a ListNode class, where val is a piece of data and next is a reference to the next node in the linked list.
Solution
Python
# Definition of a ListNodeclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = next
We can visualize a linked list as a sequence of nodes connected by arrows that point to the next node in the sequence. The first node in a linked list is referred to as the head, and the last node is referred to as the tail. The next field of the tail node is None (unless the linked list contains a cycle) which indicates the end of the linked list.
Visualization
Python
# Visualizing linked listshead = ListNode(1)head.next = ListNode(2)head.next.next = ListNode(3)head.next.next.next = ListNode(4)
0 / 4
Basic Operations
These operations demonstrate some of the fundamentals of working with linked lists.
Traversing a Linked List
When traversing a linked list, we initialize a pointer current that starts at the head node of the linked list and follows next pointers until it is None. This allows us to visit each node in the linked list, and perform operations such as finding the length of the linked list.
Visualization
Python
def findLength(head):length = 0current = headwhile current:length += 1current = current.nextreturn length
0 / 6
Complexity Analysis
Time Complexity: The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. The algorithm iterates through each node in the linked list once.
Space Complexity: The space complexity of this algorithm is O(1) since we only use one pointer to traverse the linked list regardless of the number of nodes in the linked list.
Deleting a Node With a Given Target
To delete a node with a given target, we need a reference to both the node we want to delete, and the node right before it.
We'll keep two pointers, curr and prev, and update curr until it reaches the target node, or None. We'll also update prev to be the node before curr at each step. When curr reaches the target node, we can delete it by setting prev.next = curr.next.
We have to handle deleting the head of the linked list as a special case, because there is no node before the head. We can simplify this by using a dummy node, which we'll cover later.
Visualization
Python
Try these examples:
def deleteNode(head, target):if head.val == target:return head.nextprev = Nonecurr = headwhile curr:if curr.val == target:prev.next = curr.nextbreakprev = currcurr = curr.nextreturn head
delete node with target value
0 / 6
Complexity Analysis
Time Complexity: The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. The algorithm iterates through each node in the linked list once in the worst case (when the target does not exist in the linked list).
Space Complexity: The space complexity of this algorithm is O(1) since we only use two pointers to traverse the linked list regardless of the number of nodes in the linked list.
Operations to Know for Interviews
Linked list interview questions require manipulating pointers in specific ways that depend entirely on the requirements of the problem. However, there are a few core operations that you should be familiar with, as they show up in multiple linked list questions.
This section covers those operations. At the end, we'll look at problems that will give you more practice with these operations.
1. Fast and Slow Pointers
Fast and slow pointers is a technique that is used to find the middle node in a linked list. We initialize two pointers, slow and fast, that start at the head of the linked list. We then iterate until fast reaches the end of the list. During each iteration, the slow pointer advances by one node, while the fast pointer advances by two nodes. When the fast pointer reaches tail of the list, the slow pointer points to the middle node.
Visualization
Python
def fastAndSlow(head):fast = headslow = headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextreturn slow
fast and slow pointers
0 / 4
When there are an even number of nodes, there are two possible choices for the middle node, and this technique will find the second of those two nodes.
Visualization
Python
def fastAndSlow(head):fast = headslow = headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextreturn slow
fast and slow pointers
0 / 4
It helps to make the connection between the position of the fast pointer when the iteration finishes and the condition of the while loop. For example, in the case of an odd number of nodes, the fast pointer reaches the last node of the linked list, so the while fast.next part of the loop condition is false, and the loop terminates.
In the case of an even number of nodes, the fast pointer is None (via the next pointer of the last node), so the while fast part of the loop condition is false, and the loop terminates.
In general, when working with linked list questions, having a clear understanding of what each pointer in your algorithm represents, and being able to visualize where they should end up when the iteration finishes will help you avoid off-by-one errors and null pointer exceptions.
Complexity Analysis
Time Complexity: The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. The algorithm terminates when the fast pointer reaches the end. Since fast advances two nodes per iteration, the loop runs approximately n/2 times, which is O(n).
Space Complexity: The space complexity of this algorithm is O(1) since we only use two pointers to traverse the linked list regardless of the number of nodes in the linked list.
Cycle Detection
The same fast and slow pointers technique can also be used to determine if a linked list contains a cycle. If we follow the same iteration pattern and the linked list contains a cycle, the fast pointer will eventually overlap the slow pointer and they will point to the same node.
Visualization
linked list cycle
0 / 5
This is a common interview question, and a good problem to practice using the fast and slow pointers technique (see question #1, Leetcode 141 in Practice Problems).
2. Reversing a Linked List
Reversing a linked list involves changing the direction of the next pointers in a linked list so the last node becomes the head of the reversed linked list.
The algorithm for reversing a linked list is an iterative algorithm which involves 3 pointers, prev, current, and next_.
- current points to the node we are currently reversing.
- prev is the last node that was reversed, and also the node that current.next will point to after reversing.
- next_ is the next node we will reverse. We need a pointer to this node before we overwrite the current.next so we can continue reversing the list in the next iteration.
When the iteration completes, current will be None, and prev will be the new head of the linked list.
Visualization
Python
def reverse(head):prev = Nonecurrent = headwhile current:next_ = current.nextcurrent.next = prevprev = currentcurrent = next_return prev
reverse linked list
0 / 17
Complexity Analysis
Time Complexity: The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. The algorithm iterates through each node in the linked list once.
Space Complexity: The space complexity of this algorithm is O(1) since we only use three pointers to reverse the linked list regardless of the number of nodes in the linked list.
3. Merging Two Linked Lists
The last operation is merging two linked lists. As an example of this operation, we'll look at how to merge two sorted linked lists.
As an input to this problem, we are given the heads of two sorted linked lists, l1 and l2, and we need to return the head of a new linked list that contains all the nodes from the two input linked lists in sorted order.
To merge two sorted linked lists, we start by determining the head of the merged linked list by comparing the values of l1 and l2, and setting the head to the smaller of the two nodes. We then advance l1 = l1.next or l2 = l2.next depending on which node we chose as the head of the merged linked list.
Visualization
Python
def merge_lists(l1, l2):if not l1: return l2if not l2: return l1if l1.val < l2.val:head = l1l1 = l1.nextelse:head = l2l2 = l2.nextcurrent = headwhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.nextcurrent.next = l1 or l2return head
merge two linked lists
0 / 1
Now, we can initialize a pointer tail, which represents the last node of the merged linked list. We then iterate through the two input linked lists, comparing the values of l1 and l2 at each step. We append the smaller of the two nodes to the tail of the merged linked list, and advance the pointer of the node we appended.
Visualization
Python
def merge_lists(l1, l2):if not l1: return l2if not l2: return l1if l1.val < l2.val:head = l1l1 = l1.nextelse:head = l2l2 = l2.nextcurrent = headwhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.nextcurrent.next = l1 or l2return head
head = l1; l1 = l1.next
0 / 5
When either l1 or l2 is None, we can append the remaining nodes of the other linked list to the merged linked list, and return head.
Visualization
Python
def merge_lists(l1, l2):if not l1: return l2if not l2: return l1if l1.val < l2.val:head = l1l1 = l1.nextelse:head = l2l2 = l2.nextcurrent = headwhile l1 and l2:if l1.val < l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.nextcurrent.next = l1 or l2return head
current = current.next
0 / 2
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n + m) where n and m are the number of nodes in the two input linked lists. The algorithm iterates through each node in the two linked lists once.
Space Complexity: O(1) We only use a constant amount of space to merge the two linked lists regardless of the number of nodes. This is because we are modifying the next pointers of the input linked lists, rather than creating new nodes.
Practice Problems
These practice problems will give you practice with these core operations:
Linked List Cycle
Leetcode #141 | Solution
Hint: Use fast and slow pointers to determine if a linked list contains a cycle.
Palindrome Linked List
Leetcode #234 | Solution
Hint: Use fast and slow pointers to find the middle of the linked list, and reverse the second half of the linked list, and compare the values of the nodes in the first half and the reversed second half.
Reorder List
Leetcode #143 | Solution
Hint: Use fast and slow pointers to find the middle of the linked list, reverse the second half of the linked list, and merge the two halves of the linked list together.
Dummy Nodes
Merging two sorted linked lists is an example of a problem where using a dummy node can simplify the logic of the code.
Notice that in the solution for merging two lists above, the logic for choosing the head of the merged linked list is the same as the logic for choosing the next node to append. We need to handle it as a special case because without it, we wouldn't have a starting point for the merged linked list.
We can avoid this by creating a dummy node to represent the starting point of the merged linked list. This allows us to move directly into the iteration processes without having to introduce a special case to initialize the head of the merged linked list. When the iteration finishes we return dummy.next as the head of the merged linked list.
Note: The term "dummy node" refers to creating a new node that isn't part of the input linked list(s) (line 2 in the code below).
Visualization
Python
def merge_two_lists(l1, l2):dummy = ListNode()tail = dummywhile l1 and l2:if l1.val < l2.val:tail.next = l1l1 = l1.nextelse:tail.next = l2l2 = l2.nexttail = tail.nexttail.next = l1 or l2return dummy.next
merge two linked lists
0 / 9
Advantages of a Dummy Node
The advantage of using a dummy node for this question is that it allows us to avoid having to initializing the head of the merged linked list as a special case. This simplifies the logic of the code, and also reduces the need to check if either of the merged linked lists are None (which we need to do if we don't use a dummy node because we reference either l1.next or l2.next as part of initializing the head of the merged linked list. If either l1 or l2 are None, then that reference would throw a null pointer exception).
When to Use a Dummy Node
If you find yourself writing a solution where you need to introduce a special case to initialize the head of a linked list, and the logic for handling the head is the same as the logic for handling the rest of the linked list, you should consider using a dummy node to simplify your solution.
Using a dummy node under these conditions involves the following 3 steps:
- Creating the dummy node to represent the head of the linked list you are constructing.
- Now, you can iteratively append nodes to the end that linked list based on the logic of the problem.
- Returning dummy.next as the head of the linked list you constructed.
This might be confusing, so the best way to understand this concept is through practice.
Other Use Cases
Dummy nodes can also simplify the logic of removing a node in a linked list. As we saw above, removing a node in a linked list requires a reference to the previous node of the node you want to remove. By prepending a dummy node to the head of the link list, we can ensure that each node (including the head) has a previous node, and we can avoid handling the head of the linked list as a special case.
Removing a Node in a Linked List With a Dummy Node
Visualization
Python
Try these examples:
def deleteNode(head, target):dummy = ListNode(0)dummy.next = headprev = dummycurr = headwhile curr:if curr.val == target:prev.next = curr.nextbreakprev = currcurr = curr.nextreturn dummy.next
delete node with target value
0 / 7
Practice Problems
Swap Nodes in Pairs
Leetcode #24 | Solution
Hint: Start by figuring out the pointers you need to manipulate in order to swap two nodes in the middle of a linked list, then think about how using a dummy node can simplify your solution.
Partition List
Leetcode #86
Hint: Use two dummy nodes!
Remove Nth Node From End of List
Leetcode #19 | Solution
Hint: Use a dummy node to avoid handling the case of removing the head of the linked list as a special case.
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.