Linked Lists
66 / 170Linked ListsLesson 11 of 12About 59 min
The hardest pointer surgery in the set. Everything you need is already written; the difficulty is bookkeeping.
Reverse the list in consecutive groups of k nodes. If fewer than k nodes remain at the end, leave them alone.
You can already reverse a whole list. Two things are new: reversing only a segment, and reconnecting each reversed segment to the ones on either side.
Segment reversal is the ordinary reversal loop with a counter instead of a None check, and it returns both ends of what it reversed.
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 reverse_k(head, k): """Reverse exactly k nodes. Return (new_head, new_tail, rest).""" prev, curr = None, head for _ in range(k): ahead = curr.next curr.next = prev prev = curr curr = ahead return prev, head, curr # head became the tail new_head, new_tail, rest = reverse_k(build([1, 2, 3, 4, 5]), 3)print(to_list(new_head), new_tail.val, to_list(rest))Write has_k_more and reverse_k as separate functions and test them on their own. Then the main loop is: while another full group exists, reverse it, stitch it in, and advance the predecessor to the group's new tail.
Attempting it as one function with five pointers is how this problem eats an hour. It is not conceptually hard; it is unforgiving.
One group of three is reversed and stitched to the front, and then the list is printed. The 4 and the 5 were deliberately left untouched. Type exactly what it prints.
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 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 reverse_k(head, k): prev, curr = None, head for _ in range(k): ahead = curr.next curr.next = prev prev = curr curr = ahead return prev, head, curr dummy = Node(0, build([1, 2, 3, 4, 5]))new_head, new_tail, rest = reverse_k(dummy.next, 3)dummy.next = new_head # front attachedprint(to_list(dummy.next))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.