Easy Pointer Walk Linked Lists
In plain English: Add a new node at a specific position in a linked list.
In a linked list, insertion is O(1) once you're at the right spot — the cost is in walking there.
Prompt
Insert value val at position k (0-indexed) in a linked list.
Try to write it from scratch before scrolling down.
Solution
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def insert_at(head, val, k):
new = Node(val)
if k == 0:
new.next = head
return new
cur = head
for _ in range(k - 1):
cur = cur.next
# splice new node in
new.next = cur.next
cur.next = new
return head
# Test: 1->2->3, insert 9 at k=1 => 1->9->2->3