Hard

Question 1

25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Answer 1

Using O(1) memory and O(n+n):
- Create a dummy head
- Step forward k nodes. If you reach the end, return.
- Sort the k-group. Move the first in the k-group (left-most) to the next node (cur.next) until cur is first. Repeat.

if k == 1: return head
dummy = ListNode(-1)
dummy.next = head
cur = head
prevGroupTail = dummy

    while cur:
        # save a ref to the starting node. we will set prevGroupTail to this later.
        startingNode = cur
        # move cur up to the last in the k group
        for i in range(k-1):
            if cur.next is None: return dummy.next
            cur = cur.next
        # save a ref to the next group. we set cur to this later so we don't have to step forward to it.
        nextGroupHead = cur.next
        # move the first in the k group to cur.next until cur is first
        while cur != prevGroupTail.next:
            tmp = prevGroupTail.next
            prevGroupTail.next = tmp.next
            tmp.next = cur.next
            cur.next = tmp
        prevGroupTail = startingNode
        cur = nextGroupHead         

    return dummy.next

Question 2

37. Sudoku Solver

Answer 2

Backtracking can be made more efficient by using hash sets for quickly checking which digits have already been used, and filling answers in the most constrained cells first.

I wanted to be able to quickly check which digits were available for any given cell, so I used hash sets. I used a stack of cells sorted by how many possible answers they have. Instead of working through each cell sequentially, I start backtracking from the cells that are already the most constrained (fewest possible answers). This minimizes the number of times we actually need to step backwards. This approach trades higher memory usage for shorter run time.

Time complexity: O(1)
Space complexity: O(1)