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

Traversal Linked Lists

Floyd’s cycle-finding algorithm

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Thought process:

  • Use two pointers each traversal the linked list at different ‘speed’.
  • If there is a cycle, the faster pointer will eventually intersect the slower pointer.
def has_cycle(head):
    fast, slow = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow: return True
    return False

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Thought process:

  • First detect if cycle exists or not.
  • Traversal one pointer from head and one pointer from the intersect at the same speed.
  • They will intersect at the begining of the cycle.
def detect_cycle(head):
    def has_cycle(head):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow: return slow
        return None

    intersect = has_cycle(head)
    if not intersect: return None
    node = head
    while node != intersect:
        node = node.next
        intersect = intersect.next
    return intersect

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

Thought process:

  • The problem looks like this:
A: AAAA
       CCCC
B:   BB
       ^
       |
     start of intersection
  • Traversal the two lists at the same speed, when one reaches the end, jump the pointer to the head of the other one.
  • They will reach each other at the intersection node.
AAAACCCCBBCCCC
BBCCCCAAAACCCC
          ^
          |
        start of intersection

def get_intersection_node(head_a, head_b):
    trav1, trav2 = head_a, head_b
    while trav1 != trav2:
        if not trav1: trav1 = head_b
        else: trav1 = trav1.next

        if not trav2: trav2 = head_a
        else: trav2 = trav2.next
    return trav1

Manipulate Linked Lists

203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Thought process:

  • Iterate through the linked list, when we see the next node is of the target value, short that link.
def remove_elements(head, val):
    ret = node = ListNode(None)
    node.next = head
    while node and node.next:
        if node.next.val == val: node.next = node.next.next
        else: node = node.next
    return ret.next

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Thought process:

  • Use two pointers to traversal the linked list.
  • Make them n + 1 nodes apart and advancing at same speed.
  • When the right one reaches the end, the left one is pointing at the nth node from the ned
def remove_nth_from_end(head, n):
    ret = left = ListNode(None)
    left.next = head

    right = head
    while right and n:
        right = right.next
        n -= 1

    while right:
        right = right.next
        left = left.next

    left.next = left.next.next
    return ret.next

206. Reverse Linked List

Reverse a singly linked list.

Thought process:

None     1 --> 2 --> None
 ^       ^
 |       |
prev curr=head
  • Have two pointers, pointing at the previous and current node.
  • We want the current node points backwards, have move the two pointers forward.
  • Onliner is prev, curr.next, curr = curr, prev, curr.next which is a bit tricky.
  • Or have a temp variable to be safer.
def reverse_list(head):
    prev, curr = None, head
    while curr: prev, curr.next, curr = curr, prev, curr.next
    return prev

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Thought process:

  • Move to the mth node. Keep a reference of the (m-1)th node, it has to point at the head of the reversed sub list.
  • Reverse the sublist with n - m + 1 nodes.
  • Connect the (m-1)th and (n+1)th node to the reversed sublist.
  • Remeber to handle the edge case is when m = 0.
def reverse_between(head, m, n):
    prev, trav = None, head
    while m > 1:
        prev, trav = trav, trav.next
        m, n = m - 1, n - 1

    tail, last = trav, prev

    while n:
        prev, trav.next, trav = trav, prev, trav.next
        n -= 1

    if last:
        last.next = prev
    else:
        head = prev

    tail.next = trav
    return head

369. Plus One Linked List

Given a non-negative integer represented as a linked list of digits, plus one to the integer.
The digits are stored such that the most significant digit is at the head of the list. ```python class Solution: def plusOne(self, head: ListNode) -> ListNode: def reverse(head): prev, curr = None, head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev

    head = reverse(head)

    curr, carry = head, 1
    while curr:
        carry, curr.val = divmod(curr.val + carry, 10)
        if carry and not curr.next:
            curr.next = ListNode()
        curr = curr.next

    return reverse(head) ``` Or iterative without reverse ```python class Solution:
def plusOne(self, head: ListNode) -> ListNode:
    
    sentinel = slow = ListNode(val=0, next=head)
    fast = head
    
    while fast:
        if fast.val != 9:
            slow = fast
        fast = fast.next
            
    slow.val += 1
    while slow.next:
        slow.next.val = 0
        slow = slow.next
        
    return sentinel if sentinel.val == 1 else sentinel.next ```

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

# swap
prev -> curr -> next -> beyond
prev -> next -> curr -> beyond
                prev -> curr -> next -> beyond

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        sentinel = ListNode(None, next=head)
        prev, curr = sentinel, sentinel.next
        while curr and curr.next: # has a pair of nodes to swap
            next_ = curr.next
            beyond = next_.next
            prev.next, curr.next, next_.next = next_, beyond, curr
            prev, curr = curr, curr.next
        return sentinel.next

This is a special case of the next question.

25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Thought process:

  • Iterativly reverse sublist of size k. Keep track of the head and tail of the reversed sublist.
  • Have the previous tail points to he new head, then update the pointer of previous tail.
  • Link the remaining nodes in the end.
def reverse_k_group(head, k):
    def has_k_nodes(node, k):
        while node and k:
            node = node.next
            k -= 1
        return k == 0

    def reverse_k_nodes(node, k):
        trav, prev, tail = node, None, node
        for i in range(k):
            prev, trav.next, trav = trav, prev, trav.next
        return trav, prev, tail

    ret = prev_tail = ListNode(None)
    ret.next = node = head
    while has_k_nodes(node, k):
        node, this_head, this_tail = reverse_k_nodes(node, k)
        prev_tail.next = this_head
        prev_tail = this_tail
    prev_tail.next = node
    return ret.next

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Thought process:

  • Find the middle of the linked list.
  • Reverse the second half.
  • Compare nodes one by one between the first half and reversed second half.
  • Be a nice person and undo the reverse on the second half.
def isPalindrome(head):
    if not head or not head.next: return True
    def get_midpoint(head):
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

    def reverse(head):
        prev, trav = None, head
        while trav:
            prev, trav.next, trav = trav, prev, trav.next
        return prev

    mid = reverse(get_midpoint(head))
    p, q = head, mid
    while p and q and p != q:
        if p.val != q.val:
            reverse(mid)
            return False
        else:
            p = p.next
            q = q.next
    reverse(mid)
    return True

328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

Thought process:

  • Alternativly grab values from the list and put into the right list.
def odd_even_list(head):
    even_head = even = ListNode(None)
    odd_head = odd = ListNode(None)

    odd_turn = True
    while head:
        if odd_turn:
            odd.next = head
            odd = odd.next
        else:
            even.next = head
            even = even.next

        head = head.next
        odd_turn = not odd_turn

    even.next = None
    odd.next = even_head.next
    return odd_head.next

143. Reorder List

Given a singly linked list \(L: L_0 → L_1 → … → L_{n-1} → L_n\) reorder it to: \(L_0 → L_n → L_1 → L_{n-1} → L_2 → L_{n-2} → …\)

Thought process:

  • 1->2->3->4->5 will becomes 1->5->2->4->3
  • So basically break the list into two halves(second half be one node less when we have odd number of nodes), reverse the second half, and stitch them together.
def reorder_list(head):
    def split(head):
        l1 = l2 = head
        while l2 and l2.next:
            l1 = l1.next
            l2 = l2.next.next
        middle = l1.next
        l1.next = None
        return middle

    def reverse(head):
        prev, trav = None, head
        while trav:
            prev, trav.next, trav = trav, prev, trav.next
        return prev

    if not head or not head.next: return head

    l1 = head
    l2 = reverse(split(head))
    ret = trav = ListNode(None)
    while l1 and l2:
        trav.next = l1
        l1 = l1.next
        trav = trav.next

        trav.next = l2
        l2 = l2.next
        trav = trav.next

    if l1: trav.next = l1
    return ret

138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.

Thought process:

  • If we can use hash map to keep a one to one mapping between original nodes and their copies. We can add the random pointers easily. With this method we probably need to do two pass, once to make copies and handle the regular next pointers between the copies, a second time to add the random pointers.
  • To optimize space, we won’t use hashmap, so we need to use the pointers we have to keep track of things.
  • We can do three passes.
    1. We make copies and insert them directly after original node. So the og_node.next is the copy and og_node.next.next is the orignal next node.
    2. We add the random pointers between the copies with the fact that copy.random should be og_node.random.next.
    3. We de-couple the intermingled original and copied linked list.
def copy_random_list(head):
    node = head
    while node:
        copy = Node(node.val)
        copy.next = node.next
        node.next = copy
        node = copy.next

    node = head
    while node:
        copy = node.next
        if not node.random: copy.random = None
        else: copy.random = node.random.next
        node = node.next.next

    node = head
    ret = copy = None if not head else head.next
    while node:
        node.next = copy.next
        node = node.next
        copy.next = None if not node else node.next
        copy = copy.next
    return ret

708. Insert into a Sorted Circular Linked List

Given a node from a Circular Linked List which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list, and may not be necessarily the smallest value in the circular list.

Thought process:

  • Find the insert location and insert it.
  • Its either in the middle of the cycle if the value is within bound or where the cycle starts if the value is outside the bound.
def insert(head, val):
    if not head:
        nd = ListNode(val)
        nd.next = nd
        return nd

    prev, trav = head, head.next
    while trav != head:
        if prev.val <= val <= trav.val:
            break
        elif prev.val > trav.val:
            if val >= prev.val or val <= trav.val:
                break
        prev, trav = trav, trav.next
    prev.next = ListNode(val, trav)
    return head

Merge Lists

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Thought process:

  • Traversal the two lists with two pointers.
  • Iterativly add the smaller of the two nodes to the list and advance the respective pointer.
  • Add the remainder to the end.
def merge_two_sorted_lists(l1, l2):
    ret = trav = ListNode(None)
    while l1 and l2:
        if l1.val < l2.val:
            trav.next = l1
            l1 = l1.next
        else:
            trav.next = l2
            l2 = l2.next
        trav = trav.next
    trav.next = l1 if l1 else l2
    return ret.next

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Thought process:

  • Merge lists two at a time from bottom up.
  • With k lists at the bottom, each level up, the number of lists is halved.
  • There \(log_2^K\) levels in total, each level the amount of work is \(N\), that is the overall number of nodes.
  • So the time complexity is O(Nlogk).
def merge_k_lists(self, lists: List[ListNode]) -> ListNode:
    ret = trav = ListNode(0)
    q = PriorityQueue()

    for node in lists:
        q.put((node.val, id(node), node))

    while not q.empty():
        val, _, node = q.get()
        trav.next = ListNode(val)
        trav = trav.next
        node = node.next
        if node: q.put((node.val, id(node), node))
    return ret.next

Small note on id is need to compare the case where node.val are equal, since node object is not comparable.

Small note on PriorityQueue from queue, it functionally ok, but more heavy weight than heapq in python.

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Thought process:

  • Do math one digit at a time, carry over overflows.
def add_two_numbers(l1, l2):
    carry = 0
    ret = trav = ListNode(None)

    while l1 or l2 or carry:
        if l1:
            carry += l1.val
            l1 = l1.next
        if l2:
            carry += l2.val
            l2 = l2.next
        carry, val = divmod(carry, 10)
        trav.next = ListNode(val)
        trav = trav.next
    return ret.next

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Thought process:

  • reverse the two lists.
  • add them use the code above.
  • then reverse the result.
    def add_two_numbers_ii(l1, l2):
        l1 = reverse_list(l1)
        l2 = reverse_list(l2)
        l3 = add_two_numbers(l1, l2)
        l3 = reverse_list(l3)
        return l3

1634. Add Two Polynomials Represented as Linked Lists

A polynomial linked list is a special type of linked list where every node represents a term in a polynomial expression. Each node has three attributes:

  1. coefficient: an integer representing the number multiplier of the term. The coefficient of the term 9x4 is 9.
  2. power: an integer representing the exponent. The power of the term 9x4 is 4.
  3. next: a pointer to the next node in the list, or null if it is the last node of the list. For example, the polynomial 5x3 + 4x - 7 is represented by the polynomial linked list illustrated below: img
    The polynomial linked list must be in its standard form: the polynomial must be in strictly descending order by its power value. Also, terms with a coefficient of 0 are omitted.
    Given two polynomial linked list heads, poly1 and poly2, add the polynomials together and return the head of the sum of the polynomials. PolyNode format: The input/output format is as a list of n nodes, where each node is represented as its [coefficient, power]. For example, the polynomial 5x3 + 4x - 7 would be represented as: [[5,3],[4,1],[-7,0]]. ```python class Solution: def addPoly(self, poly1: ‘PolyNode’, poly2: ‘PolyNode’) -> ‘PolyNode’: curr = sentinel = PolyNode()
    while poly1 and poly2:
        if poly1.power > poly2.power:
            curr.next = PolyNode(poly1.coefficient, poly1.power)
            curr = curr.next
            poly1 = poly1.next
        elif poly2.power > poly1.power:
            curr.next = PolyNode(poly2.coefficient, poly2.power)
            curr = curr.next
            poly2 = poly2.next
        else:
            coef = poly1.coefficient + poly2.coefficient
            if coef != 0:
                curr.next = PolyNode(coef, poly1.power)
                curr = curr.next
            poly1 = poly1.next
            poly2 = poly2.next       
    curr.next = None
    
    if poly1: curr.next = poly1
    if poly2: curr.next = poly2
    
    return sentinel.next ```

Sorting

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Thought process:

  • Do bottom up merge sort.
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if head is None: return None

        def count_nodes(node):
            """count the number of nodes in linked list starting with given node."""
            total = 0
            while node: total, node = total + 1, node.next
            return total
        
        def split(node, length):
            """From given node, cut the link at given length. Return the next node after cut. 
            
            A->B->C
            split(A, 1) will cut A->B and return B
            split(A, 2) will cut B->C and return C
            """
            while length > 1 and node: length, node = length - 1, node.next
            if node is None: return None
            temp, node.next = node.next, None
            return temp
        
        def merge(l, r, node):
            """Merge two linked list in sorted order. Return the tail."""
            while l and r:
                if l.val < r.val: node.next, l = l, l.next
                else:             node.next, r = r, r.next
                node = node.next
            node.next = l if l is not None else r
            while node.next: node = node.next
            return node

        size = count_nodes(head)
        sentinel = ListNode(None, head)
        length = 1
        while length < size:
            node, tail = sentinel.next, sentinel
            while node:
                l, r = node, split(node, length)
                node = split(r, length)
                tail = merge(l, r, tail)
            length <<= 1
        return sentinel.next

430. Flatten a Multilevel Doubly Linked List

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head: return head
        
        prev = sentinel = Node(None, None, head, None)
        stack = [head]
        while stack:
            curr = stack.pop()
            
            prev.next = curr
            curr.prev = prev
            
            if curr.next: stack.append(curr.next)
            if curr.child: 
                stack.append(curr.child)
                curr.child = None
                
            prev = curr
            
        sentinel.next.prev = None
        return sentinel.next