Linked List

Problems

Reverse list

leetcode_link

Hypothesis approach

• Assume the function solve(head) reverse’s the list with head marking start of the list.
• Next, check for smaller input. In this case, smaller input refers to list starting with head.next.
• Next, identify the relationship between the two functions.

  orig_input = 1 -> 2 -> 3
  smaller_input = 2 -> 3
  
  solve(smaller_input) = 3 -> 2
  
  solve(orig_input) = solve(smaller_input) + add '1' to the end

• Base case is empty list.

def solve(head):
    if head is None:
        return head

    prev = None
    while head:
        # need to store next element for reference
        next_node = head.next

        # do the swap
        head.next = prev
        prev = head

        # move pointer
        head = next_node
    
    return prev

Check if list is palindrome

leetcode_link

def solve(head):
    if head is None:
        return
    
    pointer = head
    fast_pointer = head

    prev = None
    while fast_pointer and fast_pointer.next:
        fast_pointer = fast_pointer.next.next

        # Reverse the first half of the list
        next_node = pointer.next
        pointer.next = prev
        prev = pointer
        pointer = next_node
    
    # prev = first half of the list (reversed)
    # pointer = second half od the list

    # Handle odd length (as pointer is at center)
    if fast_pointer:
        pointer = pointer.next

    is_palindrome = True
    while pointer:
        if prev.val != pointer.val:
            is_palindrome = False
            break
        
        prev = prev.next
        pointer = pointer.next

    return is_palindrome

Remove all occurances of val

leetcode_link

def solve(head, val):
    root = head
    prev = None
    while head:
        if head.val == val:
            if prev:
                # delete the node, prev remains the same
                prev.next = head.next
                head = prev.next
            else:
                # handle the case where val is the first node
                root = head.next
                head = root
        else:
            # just move to the next node
            prev = head
            head = head.next
    
    return root

Print immutable linked list in reverse

leetcode_link

You can only use node.printValue() and node.getNext() methods, and have to print the linked list in reverse order.

# Time = O(n^2), Space = O(1)
def solve(head):
    # Get length of list
    length = 0
    node = head
    while node:
        length += 1
        node = node.getNext()

    # Iterate to length and print the last node and repeat with length - 1
    while length > 0:
        node = head

        for _ in range(length - 1):
            node = node.getNext()
        node.printValue()

        length -= 1

# Time = O(n), Space = O(sqrt(n))
def solve(head):
    # Get length of list
    length = 0
    node = head
    while node:
        length += 1
        node = node.getNext()

    # Use SQRT decomposition to store sqrt(n) size blocks and print them in reverse
    length_sqrt = math.floor(math.sqrt(length)) # floor/ceil does not matter
    while length > 0:
        node = head

        orig_length = length
        length = max(0, length - length_sqrt)

        for _ in range(length):
            node = node.getNext()

        # Create block of size sqrt(n)
        block = []
        for _ in range(length, orig_length):
            block.append(node)
            node = node.getNext()
        
        # Print block in reverse
        for i in range(len(block)-1, -1, -1):
            block[i].printValue()

# Time = O(n logn), Space = O(logn)
def solve(head):
    helper(head, None)

# Use divide and conquer (similar to merge sort). Print the right value before left value
def helper(start_node, end_node):
    if start_node is None or start_node == end_node:
        return
    
    if start_node.getNext() == end_node:
        start_node.printValue()
        return

    # Use two slow/fast pointer to find the middle of the list
    slow = start_node
    fast = start_node

    while fast != end_node and fast.getNext() != end_node:
        slow = slow.getNext()
        fast = fast.getNext().getNext()
    
    # Call the function first with right side, and then left side
    helper(slow, end_node)
    helper(start_node, slow)