Linked List

Linked List:

Definitions:

• A nonlinear data structure consists of nodes with pointers to the next nodes.
• A linked list can be singly-linked, or doubly-linked, with just head pointer or together with tail pointer.
• For LeetCode, a singly-linked list with head pointer is usually given.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

• May fall under many patterns, such as fast and slow pointers.

General trick:

1. Sentinel head (also tail):

I create a dummy head first, modify everything after, and then return the actual head with dummy.next

dummy = ListNode(None)
head = dummy
# Do a lot of stuff with head
return dummy.next

This is useful as I can use the head as a pointer to traverse the linked list while still need to return the head of the linked list in result.

Problems:

1. Reverse Linked List

Intuition

This is a basic problem - a problem that can be become a sub-problem for a bigger task in the future LeetCode problems. This is like a formula that you have to remember, and then exploit it over and over again.

Algorithm

When dealing with Linked List, the king is pointer - something as dangerous as pointing gun to your headan object that points to the particular position of a node in the list. The number of pointers a problem requires depend on the amount of information I need at when processing each node in the list. Here, I need to know 3 pieces: the current node (obviously), the previous node to point the current node to, and the next node to move the pointer. Hence, I will use three pointers - pre, cur, and nex to keep track while traversing the list.

Complexity

• Time complexity: \(O(n)\): Traversing the whole list once.

• Space complexity: \(O(1)\): Pointers are essentially integers, taking constant memory

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Easy case:
        if head is None or head.next is None:
            return head
        
        # General case:
        pre, cur, nex = None, head, head.next
        while nex:
            cur.next = pre
            pre = cur
            cur = nex
            nex = nex.next
        cur.next = pre
        return cur

2. Reverse Nodes in k-Group

Intuition

The problem is twofold: getting the \(k^{th}\) node from the linked list (which is easy) and reverse just \(k\) nodes of the linked list, which is tricky.

I look at the algorithm to reverse the whole linked list, the hint is knowing the node right before the head of the group to point the tail to, and knowing the node right after the tail of the group to point the head to. The big problem is implementation.

For implementation, the node right before can be initialized as a dummy node first pointing to the head of the input linked list. The purpose is two fold. After all operations, the head of the return linked list can be accessed as dummy.next. Furthermore, the head of a group can be accessed as previous_to_group.next, while the node right after the group is next_to_group.next.

Algorithm

1. Initialize dummy node and previous_to_group.
2. Iterate the linked list:
   1. Get the \(k^{th}\) i.e., the tail of a group and node right after it.
   2. Reverse this k-node group.
   3. Set previous_to_group for the next iteration.
3. Return dummy.next i.e., the head of the new linked list

Step 2. is implemented as a separate method.

Complexity

• Time complexity: \(O(n)\): I need to iterate the linked list twice.

• Space complexity: \(O(1)\): I only need to store pointers.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0, head)
        previous_to_group = dummy # Node right before the group

        while True:
            kth_node = self.getKthNode(previous_to_group, k)
            if not kth_node:
                break
            next_to_group = kth_node.next

            # Reverse k nodes
            prev, curr = kth_node.next, previous_to_group.next

            while curr != next_to_group:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp
            
            temp = previous_to_group.next
            previous_to_group.next = kth_node
            previous_to_group = temp
        return dummy.next

    def getKthNode(self, current_node, k):
        while current_node and k > 0:
            current_node = current_node.next
            k -= 1
        return current_node

3. Reverse Linked List II

Intuition

I love the course “Grokking Coding Interview Pattern”. However, I have a feeling I have been scared. Reverse Linked List turns out to be a subproblem for Reverse Nodes in k-Group. The problem gives you two limits and asks you to reverse the nodes between the limits. The implementation is different from Reverse Nodes in k-Group as I reverse with range now, but the principle is exactly the same.

Algorithm

1. Initialize dummy node.
2. Iterate the linked list \(left-1\) times to get the node right before the group.
3. Get the left node of the group and reverse the connections of \(right-left+1\) nodes in the group.
4. Reconnect the new head and tail of the group to the nodes right before and right after.

Complexity

• Time complexity: \(O(n)\): I iterate the linked list exactly once.

• Space complexity: \(O(1)\): I only need to store pointers.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # Edge case
        if not head or left == right:
            return head
        
        dummy = ListNode(0, head)
        prev_of_group = dummy
        for _ in range(left-1):
            prev_of_group = prev_of_group.next
        
        # Reverse node
        prev, curr = None, prev_of_group.next
        for _ in range(right-left+1):
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        # Now prev is the head of the new group, and curr is the node right after the group
        prev_of_group.next.next = curr
        prev_of_group.next = prev
        return dummy.next

4. Reorder List

Intuition

As I am on a roll with linked list reversal, it is easy to think of the naive algorithm: just reverse the whole remaining linked list every time as I iterate from the second node to the end. This is of course a bad solution, with a time complexity of \(O(n^2)\). To do better, I realized that the result list looks as if its later half has been reversed, and then merged one by one with the first half. This is interesting as the problem can be divided into 3 subproblems, ones I already know the answer:

1. Find the middle of the linked list - fast and slow pointers.
2. Reverse a linked list - with 3 pointers.
3. Merge two linked list node by node - not mentioned before, but I showed you below (it appears simple in Python).

Algorithm

1. Get to the start of the second half of the linked list. For this problem, I need the exact start for linked list with an even number of nodes, and pass the exact middle for odd one.
2. Reverse the second half of the linked list.
3. Splice the two linked lists into one.

Complexity

• Time complexity: \(O(n)\): I iterate the linked list several times, but never nestedly.

• Space complexity: \(O(1)\): I only need to store pointers.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # Edge case - the list is guaranteed to be non-empty
        if not head.next:
            return head
        
        # General case
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # I use the Pythonic way to exchange variable. The real one
        # going on is included to demonstrate
        slow.next, slow = None, slow.next
        # temp = slow.next
        # slow.next = None
        # slow = temp
        slow = self._reverseList(slow)

        while slow and head:
            head.next, head = slow, head.next
            slow.next, slow = head, slow.next
            # temp = head.next
            # head.next = slow
            # head = temp
            # temp = slow.next
            # slow.next = head
            # slow = temp
    
    def _reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur, nex = None, head, head.next

        while nex:
            cur.next = pre
            pre = cur
            cur = nex
            nex = nex.next
        cur.next = pre
        return cur

5. Swapping Nodes in a Linked List

Intuition

I got sidetracked into thinking how to do this optimally again, and cannot come up with the obvious solution: transcribe the linked list into an array, swap in the array (which is easier), and then reconstruct the linked list. The memory complexity is \(O(n)\). I want to do so in-place, since we are in the in-place pattern of linked list. Another obvious one is iterating the linked list 2 times: first to find the \(k^{th}\) node from the start and the total number of nodes in the linked list, second to find the \(k^{th}\) node from the end. However, I was informed of an one-pass approach, using which has now came to be obvious: fast and slow pointer. So iterate the array to find the \(k^{th}\) node from the start. Now I have a pair of nodes \(k\)-nodes apart. If one pointer is placed here and one is placed at the beginning, when I increment both of them together, the later will be the \(k^{th}\) node from the end when the former goes to the end. Afterwards, swap the values the nodes (not the connections) and return the original head.

Algorithm

Two pass

1. Initialize kth_from_begin and kth_from_end to head.
2. Iterate the linked list with a pointer temp and count the number of node. Assign kth_from_begin at the correct node.
3. Subtract k from the node count to get the position of kth_from_end. Iterate the linked list to assign kth_from_end correctly.
4. Swap just the values and return the head.

One pass

1. Iterate the linked list with a pointer temp and count the number of node. Assign kth_from_begin at the correct node.
2. Initialize kth_from_begin to head.
3. Continue iterating with temp and kth_from_begin at the same time. As temp hits the first node, kth_from_begin is pointed to the correct node.
4. Swap just the values and return the head.

Complexity

• Time complexity: \(O(n)\): I iterate the linked list several times.

• Space complexity: \(O(1)\): I only need to store pointers.

Code

Two pass

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Key: Swap the values
        # Edge case - guaranteed linked list non-empty 
        if not head.next:
            return head
        count = 0
        kth_from_begin = kth_from_end = head
        temp = head
        while temp:
            if count == k - 1:
               kth_from_begin = temp 
            temp = temp.next
            count += 1
        
        # count will be 1 larger than the actual number of nodes
        node_from_end = count - k
        while node_from_end > 0:
            node_from_end -= 1
            kth_from_end = kth_from_end.next
        kth_from_begin.val, kth_from_end.val = kth_from_end.val, kth_from_begin.val
        return head

One pass

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Key: Swap the values
        # Edge case - guaranteed linked list non-empty 
        if not head.next:
            return head
        count = 0
        temp = head
        
        while count < k - 1:
            temp = temp.next
            count += 1
        
        kth_from_begin, kth_from_end = temp, head
        while temp.next:
            kth_from_end, temp = kth_from_end.next, temp.next

        kth_from_begin.val, kth_from_end.val = kth_from_end.val, kth_from_begin.val
        return head

6. Reverse Nodes in Even Length Groups

Intuition

I immediately thought of using a fast and slow pointers + keeping count of the current number of nodes in the group and the maximum number of nodes in the group. The later was correct, but the former was misguided. The objectives are the position of the last element of the previous group and the last element of the current group, which are needed for reversing. In that sense, it is sliding window, with the one side fixed at the last element of the previous group, while the other is dragged out to the last element of the current group. At each window, we check the oddity of the current number of nodes and reverse if necessary.

Algorithm

1. Initialize the left pointer and max group length.
2. Iterate the linked list starting at head.next (the first element does not need to be reversed), one window up to the max group length at a time.
3. If there are even number of nodes in the window, reverse it. Else, do nothing.
4. Return head after modification.

Complexity

• Time complexity: \(O(n)\): Iterate the linked list less than two times.

• Space complexity: \(O(n)\): Store only some integers.

Code

The shorthand reversal in Python is included in comments. While it looks awesome, I think that I should avoid it here as it makes debugging impossible and is certain to confuse my colleagues.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        group_prev = head
        curr_max_length = 2

        while group_prev.next:
            curr = group_prev
            count = 0
            
            for _ in range(curr_max_length):
                if not curr.next:
                    break
                count += 1
                curr = curr.next

            if count % 2: # Odd, do nothing
                group_prev = curr
            else:         # Even, reverse
                group_next = curr.next
                curr = group_prev.next
                
                for _ in range(count):
                    # curr.next, curr, group_next = group_next, curr.next, curr
                    curr_next = curr.next
                    curr.next = group_next
                    group_next = curr
                    curr = curr_next
                # group_prev.next.next, group_prev.next, group_prev = curr, group_next, group_prev.next
                prev_next = group_prev.next
                group_prev.next = group_next
                group_prev = prev_next
            curr_max_length += 1
        return head

7. Swap Nodes in Pairs

Intuition

The problem is straight-forward: I just need to iterate two nodes at a time and swap them. I need the right previous node and right after node to do so, so I keep track of it.

Algorithm

1. Initialize a dummy head, and previous + left_pointer from it.
2. Iterate the linked list and reverse each pair of nodes.
3. Once left_pointer reaches or goes past the end, return.

Complexity

• Time complexity: \(O(n)\): Iterate the linked list twice.

• Space complexity: \(O(1)\): Store only pointers.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # Edge case
        if not head:
            return head
        
        # General case
        dummy = ListNode(0, head)
        prev_to_group, left_pointer = dummy, dummy.next
        while left_pointer and left_pointer.next:
            right_pointer = left_pointer.next
            next_to_group = right_pointer.next
            prev_to_group.next = right_pointer
            left_pointer.next = next_to_group
            right_pointer.next = left_pointer
            prev_to_group, left_pointer = left_pointer, left_pointer.next
        return dummy.next

8. Copy List with Random Pointer

Intuition

Quick intuition: copy nodes first, copy links later. To achieve this, I need a data structure that can tell me the corresponding links that a copied node should have. The obvious one is a hash map. The rest is trivial.

Algorithm

1. Initializing a hash map to map old nodes to copied nodes. For convenience, initialize it with the first key-value pair of None:None.
2. Traverse the linked list. Create the deep copy of each node.
3. Traverse the hash map and create corresponding links for each node.

Complexity

• Time complexity: \(O(n)\): Traverse the linked list twice.

• Space complexity: \(O(n)\): The hash map needs to store the full linked list.

Code

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldToNew = {None:None}

        # 1st pass: construct nodes
        cur = head
        while cur:
            oldToNew[cur] = Node(cur.val)
            cur = cur.next
        
        # 2nd pass: construct links
        for node in oldToNew:
            if node is not None:
                oldToNew[node].next = oldToNew[node.next]
                oldToNew[node].random = oldToNew[node.random]
        
        return oldToNew[head]

9. LRU Cache

Intuition

The data structure needs to store key-value pairs. Easy, that is a hash map. The data structure needs to sort the pairs by recent usage. Okay, a queue can help to maintain the order, with the top of the queue being least recently used and the tail being most recently used. If an element is operated on, that element can just be pulled out of the queue and join back at the end. However, this is a case when an element in the middle can be randomly pulled out and needs inserting back. The normal array queue does not support that in \(O(1)\) time, so a different base data structure is needed i.e., doubly linked list, which supports removing and inserting at \(O(1)\).

Here the sentinel nodes also come in handy to prevent headache associated with capacity of 1. The head and tail pointers of the doubly linked list are initialized at these sentinel nodes instead.

Algorithm

Two helper methods insert and remove needs implementing. I am implementing it as a public method. If they need hiding from the users, they can be changed to hidden methods instead.

• ListNode:
  • __init__: Initialize with key, value, prev, and next pointer.
• LRUCache:
  • __init__: Initialize with hashmap cache, capacity, linkedlistsize (to compare with capacity) and two sentinel nodes + pointers.
  • remove: To simply remove a node from the linked list, move the destinations of the prev and next pointers of the previous and the next of a node.
  • insert: Add a node to the end of the linked list. Again, here it is just pointer manipulation.
  • get: If the node is found inside the hash map, before returning it needs removing and inserting into the queue. Else, return -1
  • put:

Complexity

• Time complexity: \(O(1)\): For all methods.

• Space complexity: \(O(\text{capacity})\): The maximum size of the hash map and the linked list.

Code

class ListNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.linkedlistsize = 0
        # head: least recently used, tail: most recently used
        self.head, self.tail = ListNode(0, 0), ListNode(0, 0)
        self.head.next, self.tail.prev = self.tail, self.head

    # Insert node at tail
    def insert(self, node):
        pre, nxt = self.tail.prev, self.tail
        node.prev, node.next = pre, nxt
        pre.next = nxt.prev = node
        self.linkedlistsize += 1

    def remove(self, node):
        pre, nxt = node.prev, node.next
        pre.next, nxt.prev = nxt, pre
        self.linkedlistsize -= 1

    def get(self, key: int) -> int:
        if key in self.cache:
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        
        if self.linkedlistsize == self.capacity:
            lru = self.head.next
            self.remove(lru)
            self.cache.pop(lru.key)

        self.cache[key] = ListNode(key, value)
        self.insert(self.cache[key])

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)