12 SEPTEMBER 2022/LEETCODE

Blind 75: Linked Lists

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:

  1. Setting our heads next pointer to nil, signifying the end of the list
  2. Setting our current node's next pointer, to the previous node
  3. 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 ๐Ÿ˜Ž


Alex Stevens

Alex Stevens

iOS Software Engineer