Linked Lists
Introduction
The description says it all. Linked Lists are kind of like arrays, but they have their own special nuances.
A linked list, is a data structure, represented as a sequence of Nodes. Typically a node contains 2 things. A value or object of some kind, and a pointer to the next node in the sequence. Linked Lists come in 2 flavors: singly-linked and doubly linked list. We will go over each of these in more depth later.
Unlike an array, lookup of values in a linked list is not a constant time operation. You must traverse the array to find what value you are looking for.
Typical examples of when you might need to use a Linked List is a queue for example. With an array, when you remove an element from the front, you must shift all the other elements. In a linked list, it is just a matter of changing the head pointer.
Singly-Linked List
With singly linked lists, we have a value, and a pointer to the next node. The first node is commonly known as the "Head", and the last node is known as the "Tail". It is worth noting the pointer to the next node is Optional, as the Tail node's pointer will be nil, representing the end of the linked list.
Let's discuss some time complexities of common singly linked list operations:
- Accessing the head of the list = O(1)
- Accessing the tail of the list = O(n)
- Accessing the middle of the list = O(n)
- Insert/Remove the head of the list = O(1)
- Insert/Remove the tail of the list = O(n) to access and then an O(1) operation
- Insert/Remove the middle of the list = O(n) to access and then an O(1) operation
- Searching for a value = O(n)
Doubly-Linked List
A doubly linked list is just like a singly linked list except it has 2 pointers in its node instead of 1. The 2nd pointer is a reference to the previous node. This gives doubly linked lists a major advantage, considering if you need to go backwards in your list it is very simple. With a singly linked list, if you need to go backwards, you need to start your search over.
Worth noting that doubly linked lists take up slightly more memory due to the 2nd pointer.
Let's discuss some time complexities of common doubly linked list operations:
- Accessing the head of the list = O(1)
- Accessing the tail of the list = O(1)
- Accessing the middle of the list = O(n)
- Insert/Remove the head of the list = O(1)
- Insert/Remove the tail of the list = O(1)
- Insert/Remove the middle of the list = O(n) to access and then an O(1) operation
- Searching for a value = O(n)
Slightly faster on some operations!
Also I would like to briefly touch on circular linked lists. This is where there is no clear head or tail, because the tail points to its head. Can be singly or doubly linked in these situations.
Code Representation
Although implementing a Linked List in an interview is a very rare occurrence, it still helps to know how it works under the hood from a code perspective.
Singly Linked List Node
public class Node {
var value: String
var next: Node? // Note the optionality here
public init(value: Int) {
self.value = value
}
}
Doubly Linked List Node
public class Node {
var value: String
var next: Node?
weak var previous: Node? // Note the weak ownership here to avoid a retain cycle
public init(value: Int) {
self.value = value
}
}
Linked List Class
public class LinkedList {
private var head: Node?
// Helpers
public var isEmpty: Bool {
return head == nil
}
public var first: Node? {
return head
}
public var last: Node? {
guard var node = head else { return nil }
while let next = node.next { node = next }
return node
}
// Operations
public func append(value: T) {
let newNode = Node(value: value)
if let lastNode = last {
newNode.previous = lastNode
lastNode.next = newNode
} else {
head = newNode
}
}
// Get node at a certain index
public func node(atIndex index: Int) -> Node {
if index == 0 {
return head!
} else {
var node = head!.next
for _ in 1..<index {
node = node?.next
if node == nil { //(*1)
break
}
}
return node!
}
}
// Insert at a certain index
public func insert(_ node: Node, atIndex index: Int) {
let newNode = node
if index == 0 {
newNode.next = head
head?.previous = newNode
head = newNode
} else {
let prev = self.node(atIndex: index-1)
let next = prev.next
newNode.previous = prev
newNode.next = prev.next
prev.next = newNode
next?.previous = newNode
}
}
// Remove a node
public func remove(node: Node) -> T {
let prev = node.previous
let next = node.next
if let prev = prev {
prev.next = next
} else {
head = next
}
next?.previous = prev
node.previous = nil
node.next = nil
return node.value
}
}
Not too bad! We cover some simple linked list operations here that will play into some more in depth Leetcode problems down the line.
Common Linked List Operations
It will help us in the future if we remember how some common linked list operations work, even if we remember them in english.
Delete a Node
To delete a node from a linked list, we have different tactics for singly vs doubly linked list:
- Singly Linked List: For node N, find the previous node, and set previous.next = n.next
- Doubly Linked List: For node N, set n.next.previous = n.previous
Runner Technique
Commonly in Linked Lists you will find the need to use the runner technique. This technique is implemented by having 2 pointers at the same time in your list. One pointer will move ahead of the either. You can either do: - Fast node moves by fixed amount - For every 1 move of the slow pointer, the fast pointer jumps multiple nodes.
This is commonly used for finding cycles within your linked list.
Last overview point to make about Linked List is that a lot of leetcode linked list problems rely on recursion. When solving problems, remember recursive solutions automatically add O(N) space due to the ever expanding call stack of the function.
Reverse Linked List
Time to start the foundation of our linked list knowledge!
This is a classic LinkedList problem, and is honestly really fun to reverse engineer. Learning how to reverse a linked list will set us up for success later down the road with other leetcode problems.
[ Recursive ]
[ O(n) worst time + O(n) space ]
Remember what we said earlier! A lot of Linked List problems can be solved recursively (with a hit on our space complexity due to the call stack.)
When I think about recursive problems, I like to start with the base case. In our case, the base case is if the linked list is empty, or only has 1 node. If that is the case there is nothing to reverse!
Now if we look at the recursive case, when we have 2 nodes, we know we will need to reverse the order of them. That means doing 3 things:
- Setting our heads next pointer to nil, signifying the end of the list
- Setting our current node's next pointer, to the previous node
- Setting our current node to the next node
Let's run thru an example for this. Say we have a list of [1->2]. Keep in mind we will be recursing, so we are working from the back to the front. In this example our current node is 2, and our head is 1. We want to set our heads next pointer to nil, signifying the end of the list. This makes our linked list now [1 2] with no next pointer on 1. We also want to set our current nodes next pointer, to the previous pointer. This makes our linked list now [1<-2]. And we want to set our current node to the next node, which would end our loop. Boom! It is reversed. Let's think about the pseudocode here.
if our list is empty or there is only 1 node
return the head
recurse on the rest of the linked list (the next node from head)
our current node is heads next
current nodes next is the head
heads next is nil
return the recursed rest of the linked list
Very wordy! Our space complexity here is O(n) due to the recursive call stack. Keeping references to nodes is O(1) space. The time complexity here is O(n) where n is the number of nodes in our linked list. This is because we need to visit every node to reverse them.
Here is the fully flushed out code solution:
// Base Case
if head == nil || head?.next == nil { return head }
// Recursive Case
let newHead = reverseList(head.next)
let nextNode = head.next
nextNode?.next = head
head.next = nil
return newHead
[ Iterative ]
[ O(n) time + O(1) space ]
I personally feel it is easier to derive the iterative solution for this problem.
The idea behind the iterative solution, is we have a buffer for the previous node (since this is a singly linked list, we don't know what the previous node will be at every round of iteration.), and we follow similar patterns for the recursive solution, to reverse the list. It would look something like this:
previous node is nil
current node is the head
while there is a node next to our current
set current nodes next pointer to the previous node
set previous to current node
set current node to next node
at the end of our loop, set the final nodes pointer to the previous node
return the current node
The trick here is using a while let loop to capture the next node at every iteration. The space complexity is much reduced here, as we only have 2 variables to hold references to nodes. This equals O(1) space. The time complexity is O(n) because we just need to traverse the linked list once.
Here is the final implementation:
guard head?.next != nil else { return head } // edge cases
var previous: ListNode? = nil
var current: ListNode? = head
while let nextNode = current?.next { // capture the next node
current?.next = previous
previous = current
current = nextNode
}
current?.next = previous // complete the sequence
return current
Not so bad right? On to the next!
Merge Two Sorted Lists
Here is another essential & common problem when it comes to linked lists!
After looking at this problem it seems pretty straight forward. There is not really a brute force solution to be discussed here, so let's dive into the approach.
[ Dummy Node + 2 pointers ]
[ O(n) worst time + O(n) space ]
So the idea here is straight forward enough, we just need to be careful when it comes to implementation.
First off, we need a dummy node that we will be building our return result around. Ultimately we do not care about the dummy node, but everything after it. Hence we will be returning dummy nodes next node. We will also need 2 pointers to keep track of our progress of adding nodes from linked list 1 & 2. As we add values to our return result, we will move our pointers to not add duplicate values.
At each iteration, we want to compare the values from lists 1 & 2. If they are equal, add both to the result. Otherwise we will be adding the smaller of the 2 nodes.
After we run out of nodes to add in one list, we want to make sure we get all the nodes from the remaining list, and vice versa.
Here is the pseudocode!
while in range of list one AND list 2
if the value of the node in list 1 is equal to the node value in list 2
add both to the result
move pointers in both lists
else if node 1 value < node 2 value
add node 1 to result
move node 1 pointer
else
add node 2 to result
move node 2 pointer
while list 1 pointer is not at the end of list 1
add node to result
while list 2 pointer is not at the end of list 2
add node to result
return dummy.next
As we can see here there are many loops! But luckily they are sequential and not nested, so it doesn't hurt our time complexity. The time complexity here is O(n) where n is the length of the combination of the 2 lists. If our input lists are of length 3 and 4 respectively, we know we will be looping 7 times. Our space complexity is O(n) at the worst. n is representative of the return result, as our result will continue to grow and take up space as we iterate. Our pointers do not take up memory because under the hood, the list node we are storing as a pointer is just an address in memory. Not a representation of all nodes at a given time.
Here is the final implementation.
if list1 == nil { return list2 } // edge case
if list2 == nil { return list1 } // edge case
var listOnePointer = list1
var listTwoPointer = list2
var newList = ListNode() // our dummy node
var newListPointer: ListNode? = newList // our pointer in our new list
while listOnePointer != nil, listTwoPointer != nil { // while both are in range
guard let listOnePointerValue = listOnePointer?.val, let listTwoPointerValue = listTwoPointer?.val else { break }
if listOnePointerValue == listTwoPointerValue { // equal value
// add both to the result
newListPointer?.next = ListNode(listOnePointerValue)
newListPointer = newListPointer?.next
newListPointer?.next = ListNode(listOnePointerValue)
newListPointer = newListPointer?.next
// move our pointers
listOnePointer = listOnePointer?.next
listTwoPointer = listTwoPointer?.next
} else if listOnePointerValue < listTwoPointerValue {
// add to result
let newNode = ListNode(listOnePointerValue)
newListPointer?.next = newNode
newListPointer = newListPointer?.next
// move pointer
listOnePointer = listOnePointer?.next
} else {
// add to result
let newNode = ListNode(listTwoPointerValue)
newListPointer?.next = newNode
newListPointer = newListPointer?.next
// move pointer
listTwoPointer = listTwoPointer?.next
}
}
// Finish off the stragglers
while listOnePointer != nil {
guard let listOnePointerValue = listOnePointer?.val else { break }
let newNode = ListNode(listOnePointerValue)
newListPointer?.next = newNode
newListPointer = newListPointer?.next
listOnePointer = listOnePointer?.next
}
while listTwoPointer != nil {
guard let listTwoPointerValue = listTwoPointer?.val else { break }
let newNode = ListNode(listTwoPointerValue)
newListPointer?.next = newNode
newListPointer = newListPointer?.next
listTwoPointer = listTwoPointer?.next
}
return newList.next
Well done! With linked list problems we need to be aware of any out of bounds exceptions, or nil values on a nodes next pointer.
Reorder List
This problem does a good job combining our previous 2 problems into one
Getting a little tricky! There are 2 main components to this problem we will work through together.
[ Reverse + Merge ]
[ O(n) worst time + O(n) space ]
So there are 3 parts to this problem.
The first problem is, we need to somehow get to the middle of the list so that we fill in our new list as specified, with the first node, then last node, then 2nd node, etc. Since this is a singly linked list we do not have any access to the previous node values. In order to get to the middle of the list, we can use the runner technique where we have a fast and slow pointer. We move the slow pointer 1 at a time, and the fast pointer 2 nodes at a time. When the fast node gets to the end, we know our slow pointer is in the middle of our list. This will work for both even and odd numbered linked lists. Pseudocode:
start slow at the beginning
start fast at the 2nd node
while fast pointer is not nil AND fast pointers next is not nil
move slow by 1
move fast by 2
Easy Enough!
The second part of this problem, is now that we are in the middle of our list, we know what the second half of our list is. It is everything to the right of the slow pointer. We need to reverse this portion of our list in place. This is so we split our original list up into 2 parts. A normal front half, and a reversed second half, so we can merge the 2 accordingly. ALSO, it is important we break the pointer between the first & reversed second half, so we don't have any circular lists in the future. Like this:
get second half of list from slow pointer
keep track of a previous node
while our secondHalfs next is not nil
secondHalfs next to previous
set previous to current
set current to next
set secondHalfs next to previous
set slowPointers next to nil
Ok. Cool.
The final part of the solution is merging the 2 lists together. We can say our firstHalf is the head of our linked list. This is because we broke off the slow pointers next node, thus breaking the list in half. The secondHalf is the reversed list we just created. Now, we will fill in the lists alternating from the firstHalf and secondHalf
get firstHalf
get secondHalf
create new list with dummy node
set head pointer to new list head
while we havent gotten to the end of firstHalf AND we havent gotten to the end of secondHalf
set new lists next to first half
move first half to next
move new list pointer to next
set new lists next to second half
move second half to next
move new list pointer to next
if there are leftovers in firstHalf
add them to new list
if there are leftovers in secondHalf
add them to new list
return the head pointers next
This part can get a little tricky! We need to keep edge cases in mind. Bringing it all together, we have this pseudocode solution:
// 1.
start slow at the beginning
start fast at the 2nd node
while fast pointer is not nil AND fast pointers next is not nil
move slow by 1
move fast by 2
// 2.
get second half of list from slow pointer
keep track of a previous node
while our secondHalfs next is not nil
secondHalfs next to previous
set previous to current
set current to next
set secondHalfs next to previous
set slowPointers next to nil
// 3.
get firstHalf
get secondHalf
create new list with dummy node
set head pointer to new list head
while we havent gotten to the end of firstHalf AND we havent gotten to the end of secondHalf
set new lists next to first half
move first half to next
move new list pointer to next
set new lists next to second half
move second half to next
move new list pointer to next
if there are leftovers in firstHalf
add them to new list
if there are leftovers in secondHalf
add them to new list
return the head pointers next
This is very verbose! But gets the point across. We can see there a dummy list being built and returned, and that takes up O(N) space. The time complexity on average is O(n) because we traverse the list about 3 times but never in a nested fashion.
Let's take a look at the implementation! I am a fan of readable code, even if that means your Leetcode runtime is not 0 milliseconds.
Implementation:
var slowPointer: ListNode? = head
var fastPointer: ListNode? = head?.next
// 1. Get our our fast pointer to the end and our slow pointer to the middle
while fastPointer != nil && fastPointer?.next != nil {
slowPointer = slowPointer?.next
fastPointer = fastPointer?.next?.next
}
// 2. Reverse the second half
var secondHalf = slowPointer?.next
var previous: ListNode? = nil
while let next = secondHalf?.next {
secondHalf?.next = previous
previous = secondHalf
secondHalf = next
}
secondHalf?.next = previous
let reversedList = secondHalf
slowPointer?.next = nil
// 3. Merge the two
var firstHalf = head
var secondHalf = reversedList
var merged:ListNode? = ListNode(0) // new list
let head = merged // pointer to new list
while firstHalf != nil && secondHalf != nil {
merged?.next = firstHalf
firstHalf = firstHalf?.next
merged = merged?.next
merged?.next = secondHalf
secondHalf = secondHalf?.next
merged = merged?.next
}
if let leftOver = firstHalf {
merged?.next = leftOver
}
if let leftOver = secondHalf {
merged?.next = leftOver
}
return head?.next // return dummys next
Whew! That was a doozy. But you can see it combines our first 2 leetcode problems in this section into its own problem.
Remove Nth Node From End of List
Let's move on to something a little easier!
This one is tricky! But once we figure out the trick, it is very straight forward & easy to implement in code.
[ Runner Technique ]
[ O(n) time + O(1) space ]
So the trick here is figuring out how we know we are currently at the Nth node from the end of the list. We know how to remove a node, we just need to get to the right node to remove. For this we can use the linked list runner technique. We can use a fast pointer & a slow pointer. If we set the fast pointer N spots ahead of the slow pointer, then move them both ahead by one node, when the fast pointer is at the end of the list the slow pointer will be N nodes from the end of the list! Once we get that implementation down, we know it is all about testing the edge cases after that.
Essentially it will look something like this:
move fast pointer N steps ahead
while fast pointer is not nil
move both slow & fast ahead by 1
remove the slow pointer node
So as we can see, we only traverse the list one time, and removing a node is an O(1) time operation. This equates to O(n) time where n is the length of the linked list. When it comes to space complexity, we are only keeping 3 or 4 variables tracking fast and slow pointers. These variables do not grow in space so it is safe to assume they are O(1) space complexity.
Time to implement! One thing to keep in mind here though. There are some edge cases at play. If the head node is nil, or only has 1 node we should just return nil because we are removing the only node we have in the entire list. If by the time we move our fast node to the end of the list, and our slow pointer is still at the head, we can just return head.next, since we need to remove the first node in the list. This situation will happen when we have an input variable of N that is greater than or equal to the length of the linked list.
Here is the implementation:
guard head != nil, head?.next != nil else { return nil } // Edge Case #1
var headPointer = head
var slow = head
var fast = head
var previous: ListNode? = nil
// Move fast pointer n steps ahead
for _ in 0..<n {
fast = fast?.next
}
while fast != nil { // Move fast to end, and keep track of previous along the way
previous = slow
slow = slow?.next
fast = fast?.next
}
if slow === head { return slow?.next } // Edge Case #2
// Remove the slow node
previous?.next = slow?.next
slow?.next = nil
return headPointer
Not too bad, and I hope by now Linked Lists are getting a little easier to digest. Only 2 more to go!
Linked List Cycle
This one is an all time classic!
[ Runner Technique ]
[ O(n) time + O(1) space ]
So I kind of gave away the answer to this one at the beginning of this article but we can go through the problem regardless.
The approach here is to use 2 runners & use the runner technique to see if there is a cycle in the list. We would essentially have a fast runner, and a slow runner. We move the slow pointer by 1, and the fast pointer by 2. If those 2 values are ever the same we know there is a cycle, but if we traverse to the end of the list with our fast pointer we know there is not a cycle. Something like this:
fast pointer starting at head
slow pointer starting at head
while fast is not at the end of the list
move slow by 1
move fast by 2
if slow equals fast, return true
return false
Very straight forward. I want to touch on how we would compare the 2 nodes though. We could compare the 2 node values, but that wouldn't help if our list has nodes with multiple of the same value. We could conform the node class to Equatable which gives us a way of determining the equality of 2 different class instances. But by far the easiest way in this situation, is to use the built in Swift === operator. The 3 equals sign operator compares if 2 objects share the same reference in memory. That is a sure fire way to determine if 2 nodes are the same.
The time complexity here is on average O(n) since we need to traverse the list 1 time when there is not a cycle, and 1 time + some change when there is a cycle. This averages out to O(n) time. The space complexity is O(1) since we do not have any data structures to hold our data, we just have 2 pointers which are constant time.
Let's check out the implementation!
var slow: ListNode? = head
var fast: ListNode? = head
while fast?.next != nil { // While fast is not at the end of the list
slow = slow?.next
fast = fast?.next?.next
if slow === fast { return true } // Compare fast & slow memory references
}
return false
I hope that was an easy one for you!
Merge K Sorted Lists
Lets finish off this linked list section strong! Here is a bit of a toughie:
[ Merge Sort ]
[ O(NLogK) time + O(N) space ]
So if you haven't guessed already, this problem is an extension of our previous Merge Two Sorted Lists problem. This problem is exactly the same, except instead of 2 lists we have an unknown number of K lists.
A brute force solution to this problem would be to iterate through all lists, and find the proper location for the nodes, and merge. This is a lot of repeated and unnecessary work though.
We can be a little smarter and use a variation of Merge Sort. Say our K lists we want to merge are [1], [2], [5], [3]. The brute force way is to merge [2] into [1]. Then merge [5], into [1, 2]. To do this we iterate through the 1 node and 2 node. Then we repeat that work when we want to merge 3 into [1, 2, 5]. We iterate from 1 to 2 and insert 3. How can we be more efficient?
With our same example we can use Merge Sort. Lets say our input is once again [1], [2], [5], [3]. Instead of repeating work, we can merge 1 & 2, then merge 5 & 3. Now our K lists are [1, 2], [3, 5]. Then we can merge those 2 and get [1, 2, 3, 5]. That time we only merge 2 times, and we do not do repeated work.
Something like this:
while the count of the K lists is greater than 1
keep an array for our merged lists
for every other list in k
get list 1
get list 2
merge them
add to our merged lists array
set k lists equal to merged lists
return first in k lists
The best part about this solution, is we already know how to merge 2 lists, so the only net-new code here from our previous problem, is keeping track of the current merged lists at each iteration. The time complexity here is O(NLogK), we are taking our lists, dividing them by 2 every time. We also need to iterate through every node, at every step of the way. This time comes out to O(KLogN) where N is the number of nodes in all lists, and k is the number of lists in the input. Space complexity is O(k), due to us keeping track of all the nodes in each merge iteration.
Lets check out the real iteration (this time, with a slightly different way of merging 2 lists ๐)
public class ListNode {
public var val: Int
public var next: ListNode?
public init() { self.val = 0; self.next = nil; }
public init(_ val: Int) { self.val = val; self.next = nil; }
public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}
func mergeKLists(_ lists: [ListNode?]) โ ListNode? {
if lists.isEmpty { return nil }
if lists.count == 1 { return lists.first! }
var currLists = lists
while currLists.count ๏นฅ 1 {
var mergedLists = [ListNode?]()
for i in stride(from: 0, to: currLists.count, by: 2) {
var listOne = currLists[i]
var listTwo: ListNode? = nil
if (i + 1) ๏นค currLists.count { listTwo = currLists[i + 1] }
mergedLists.append(self.mergeLists(listOne, listTwo))
}
currLists = mergedLists
}
return currLists[0]
}
func mergeLists(_ listOne: ListNode?, _ listTwo: ListNode?) โ ListNode? {
var dummy = ListNode()
var tail: ListNode? = dummy
var listOne = listOne
var listTwo = listTwo
while listOne != nil, listTwo != nil {
if listOne!.val < listTwo!.val {
tail?.next = listOne
listOne = listOne!.next
}
else {
tail?.next = listTwo
listTwo = listTwo!.next
}
tail = tail?.next
}
if listOne != nil { tail?.next = listOne }
if listTwo != nil { tail?.next = listTwo }
return dummy.next
}
Nicely done!
Conclusion
Not too bad! Come back to these problems anytime you need a friendly linked list refresher ๐