class ListNode(object): def __init__(self, val=None): self.val = val self.next = None
Traversal Linked Lists
Given a linked list, determine if it has a cycle in it.
- 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
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
- 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
Write a program to find the node at which the intersection of two singly linked lists begins.
- 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
Remove all elements from a linked list of integers that have value val.
- 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
Given a linked list, remove the n-th node from the end of list and return its head.
- Use two pointers to traversal the linked list.
- Make them
n + 1nodes 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
Reverse a singly linked list.
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.nextwhich 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
Reverse a linked list from position m to n. Do it in one-pass.
- 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 + 1nodes.
- 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
Given a linked list, swap every two adjacent nodes and return its head.
- Draw a diagram to figure out how to change the pointers.
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.
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.
- 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
Given a singly linked list, determine if it is a palindrome.
- 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
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.
- 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
Given a singly linked list reorder it to:
- 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
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.
- 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.nextis the copy and
og_node.next.nextis the orignal next node.
- We add the random pointers between the copies with the fact that
- We de-couple 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
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.
- 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 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.
- 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
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
- 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 levels in total, each level the amount of work is , 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
idis need to compare the case where
node.valare equal, since
nodeobject is not comparable.
Small note on
queue, it functionally ok, but more heavy weight than
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.
- 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
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.
- 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
Sort a linked list in O(n log n) time using constant space complexity.
- 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