Linked List

A linear collection of data elements whose order is not given by their physical placement in memory. Memory storage does not have to be contiguous as each element contains an address to the next element.

Common Questions

Reverse Linked list
Linked List Cycle
Merge Two Sorted Lists
Remove Nth Node From End of List

Time Complexity

Operation	Big-O	Note
Access	O(n)	Must traverse from start
Search	O(n)
Insert	O(1)	Assuming you are at the node of insertion
Remove	O(1)	Assuming you are at the node of deletion

Common Approaches to Linked List Questions

• Counting number of nodes in the linked list O(n)
• Reversing a linked list in-place
• Merging two linked lists together
• Finding the middle node of the linked list using two pointers

Corner cases

• Empty linked list
• Cycles in linked list

Example Solutions

Reverse Linked list

Solution 1: Recursive Approach

# linkedList = [1, 2, 3, 4, 5]

def reverseList(self, head):
    # Base case: if 0 or 1 element return that element
    if not head or not head.next:
        return head
    last = self.reverseList(head.next) # [5, 4, 3, 2]
    head.next.next = head # [2] -> [1]
    head.next = None # [1] -> None
    return last # [5, 4, 3, 2, 1]

Time Complexity: O(n) for looping through the linked list.

Space Complexity: O(n) for recursive stack of size n.

Solution 2: Iterative Approach (Prefered Solution)

def reverseList(self, head):
    prev = None
    while head:
        curr = head # curr = [1]
        head = head.next # head = [2]
        curr.next = prev # [1](curr) -> None(prev)
        prev = curr # prev = [1]
    return prev

Time Complexity: O(n) for looping through the linked list.

Space Complexity: O(1) for constant variables.

Linked List Cycle

Solution: Two Pointers

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def hasCycle(self, head):
    fast = slow = head
    while fast and fast.next: # only need to check fast pointer as it is in front of slow pointer
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            return True
    return False

Time Complexity: O(n). See here

• Case 1: No cycle
  • Fast pointer reaches the end in n/2 steps => O(n)
• Case 2: Cycle exists
  • Once the slower node reaches the cycle, the faster node catches up to the slower node in k steps, where k is the length of cycle. O((n - k) + k) => O(n)

Space Complexity: O(1) for 2 constant variables fast and slow.

Remove Nth Node From End of List

tip

Excellent leetcode explanation by sgallivan.

Solution: Two Pointers

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def removeNthFromEnd(self, head, n):
    fast = slow = head
    # Move fast pointer first
    for _ in range(n):
        fast = fast.next
    # Edge case: n == len(list), remove first node
    if not fast:
        return head.next
    # Move both pointer until fast reaches the end
    while fast.next:
        slow = slow.next
        fast = fast.next
    # Remove nth node
    slow.next = slow.next.next
    return head

Edge case explanation: when n == len(list), we want to remove the first node. fast would reach the end of the list and be equal to None, hence we check that fast == None.

Time Complexity: O(n) as it is a one pass algorithm.

Space Complexity: O(1) for 2 constant variables fast and slow.