Linked List

Question 1

Implement

Standard in-place linked list reversal algorithm
Input: head
Output: head with linked list reversed

Answer 1

def reverse(head):
    prev = None
    curr = head

    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        
    return prev

Question 2

Implement

In-place linked list reversal of the first K nodes algorithm
Input: head, int k that is guaranteed to be within range of the length of the linked list
Output: new head with linked list reversed

Answer 2

def reverse(head, k):
    if head is None:
        return head

    prev = None
    curr = head
    
    for _ in range(k):
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        
    head.next = curr
    return prev

## Footnote

This is guaranteed to work EVEN IN A SINGLE LONELY NODE

Question 3

Implement

In-Place Linked List Reversal Between Start and End Position algorithm
Input: head, int start and int end where 1 <= start <= end and both ints guaranteed to be within range of the length of the linked list; 1 means the first node (i.e. head)
Output: new head with specified range of nodes reversed

Answer 3

def reverse(head, k):
    prev = None
    curr = head
    
    for _ in range(k):
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
        
    head.next = curr
    return prev

def reverse_between(head, left, right):
  dummy = ListNode(next=head)
  prev = dummy
  for _ in range(left - 1):
      prev = prev.next
      
  start = prev.next
  
  new_prev = reverse(start, right - left + 1)
  prev.next = new_prev
 
  return dummy.next

## Footnote

The reverse() function is an EXACT copy of the reverse function for “In-Place Linked List Reversal of the First K Nodes”

Question 4

Given the head of a linked list, return the middle node. If the number of nodes in the in the list is even, return the first/earlier of the 2 nodes.

Answer 4

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

    slow, fast = head, head

    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next
    
    return slow

Note the fast.next is ALWAYS needed for the odd cases. To make it easy to think, just use the test case of 1 node or 2 nodes. WLOG, it works in other cases

Question 5

Given the head of a linked list, return the middle node. If the number of nodes in the in the list is even, return the second/later of the 2 nodes.

Answer 5

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

    slow, fast = head, head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
    
    return slow

Note the fast.next is ALWAYS needed for the odd cases. To make it easy to think, just use the test case of 1 node or 2 nodes. WLOG, it works in other cases