Linked Lists
class ListNode(object):
def __init__(self, val=None):
self.val = val
self.next = None
Traversal Linked Lists
Floyd’s cyclefinding 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 nth 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 trav=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, trav.next, trav = trav, prev, trav.next
which is a bit tricky.  Or have a temp variable to be safer.
def reverse_list(head):
prev, trav = None, head
while trav:
prev, trav.next, trav = trav, prev, trav.next
return prev
92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in onepass.
Thought process:
 Move to the mth node. Keep a reference of the (m1)th node, it has to point at the head of the reversed sub list.
 Reverse the sublist with
n  m + 1
nodes.  Connect the (m1)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
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
Thought process:
 Draw a diagram to figure out how to change the pointers.
 Initial:
None > 1 > 2 > 3 ^ ^   prev head
a = pre.next; b = a.next
None > 1 > 2 > 3 ^ ^ ^    prev a b
prev.next = b
None  ^ v  1 > 2 > 3  ^ ^    prev a b
a.next = b.next
None  ^            v v  1 2 > 3  ^ ^    prev a b
b.next = a
None  ^            v v  1 < 2 3  ^ ^    prev a b
 Rearrange the graph:
None > 2 > 1 > 3 ^ ^ ^    prev b a
pre = a
None > 2 > 1 > 3 ^ ^   b a = pre
def swap_pairs(head):
ret = pre = ListNode(None)
pre.next = head
while pre.next and pre.next.next:
a = pre.next
b = a.next
pre.next, a.next, b.next = b, b.next, a
pre = a
return ret.next
This is a special case of the next question.
25. Reverse Nodes in kGroup
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 leftout 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_{n1} → L_n\) reorder it to: \(L_0 → L_n → L_1 → L_{n1} → L_2 → L_{n2} → …\)
Thought process:
1>2>3>4>5
will becomes1>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.
 We make copies and insert them directly after original node. So the
og_node.next
is the copy andog_node.next.next
is the orignal next node.  We add the random pointers between the copies with the fact that
copy.random
should beog_node.random.next
.  We decouple the intermingled original and copied linked list.
 We make copies and insert them directly after original node. So the
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 wherenode.val
are equal, sincenode
object is not comparable.
Small note on
PriorityQueue
fromqueue
, it functionally ok, but more heavy weight thanheapq
in python.
2. Add Two Numbers
You are given two nonempty linked lists representing two nonnegative 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 nonempty linked lists representing two nonnegative 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
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.
def sort_list(head):
if head is None: return None
def get_size(node):
size = 0
while node:
size +=1
node = node.next
return size
def split(node, n):
i = 1
while i < n and node:
node = node.next
i += 1
if node is None: return None
tail, node.next = node.next, None
return tail
def merge(l, r, node):
trav = node
while l and r:
if l.val < r.val: trav.next, l = l, l.next
else: trav.next, r = r, r.next
trav = trav.next
trav.next = l if l is not None else r
while trav.next: trav = trav.next
return trav
size = get_size(head)
sublist_size = 1
ret = ListNode(None)
ret.next = head
while sublist_size < size:
trav = ret.next
prev = ret
while trav:
l = trav
r = split(l, sublist_size)
trav = split(r, sublist_size)
prev = merge(l, r, prev)
sublist_size <<= 1
return ret.next