Linked Lists
60 / 170Linked ListsLesson 5 of 12About 71 min
The hard-looking problems in this unit are usually three easy ones in a row.
Here is a different rearrangement built the same way: move the second half of a list to the front, keeping both halves in order.
class Node: def __init__(self, val, next=None): self.val, self.next = val, next def build(values): head = None for value in reversed(values): head = Node(value, head) return head def to_list(node): out = [] while node: out.append(node.val) node = node.next return out def split_at_middle(head): """Split in two, giving the first half the extra node when odd.""" if head is None or head.next is None: return head, None slow, fast = head, head.next # offset start gives the first middle while fast and fast.next: slow = slow.next fast = fast.next.next second = slow.next slow.next = None # the cut, and it must happen return head, second def append(first, second): if first is None: return second tail = first while tail.next: tail = tail.next tail.next = second return first def rotate_halves(head): first, second = split_at_middle(head) return append(second, first) print(to_list(rotate_halves(build([1, 2, 3, 4]))))print(to_list(rotate_halves(build([1, 2, 3, 4, 5]))))For the problem below, write down the sequence of operations first, in words. Something like: find the middle, cut, reverse the second part, then interleave.
With that written down it is three functions you have already built and one loop to write. Without it, it is a single enormous function with four pointers and no way to tell which one is wrong.
Build the three operations separately so the composition is assembly. reverse reverses a list and returns the new head. split_at_middle returns the two halves, giving the first the extra node when the length is odd, and cuts the link between them. interleave alternates nodes from two lists, starting with the first, and appends anything left over.
Tests
print(to_list(reverse(build([1, 2, 3]))), to_list(reverse(build([]))))a, b = split_at_middle(build([1, 2, 3, 4]))print(to_list(a), to_list(b))a, b = split_at_middle(build([1, 2, 3, 4, 5]))print(to_list(a), to_list(b))print(to_list(interleave(build([1, 2]), build([9, 8]))))print(to_list(interleave(build([1]), build([9, 8, 7]))))Output
Run tests to see output.
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.