Linked List Patterns

2025-04-14 23:56

Find the middle

slow, fast = head, head
while fast and fast.next:
	slow = slow.next
	fast = fast.next.next
# slow ptr will have the middle node

Reverse the list

prev, curr = None, head
while curr:
	nxt = curr.next
	curr.next = prev
	prev = curr
	curr = nxt

Merge two array (Cross One)

a = [1,2,3,4]
b = ['a','b','c']
# after merge
new_arr = [1, 'a', 2, 'b', 3, 'c', 4]

# logic
first, second = head1, head2
while second:
	tmp1, tmp2 = first.next, second.next
	first.next = second
	second.next = tmp1
	first, second = tmp1, tmp2

Reorder a Linked List

Ask is to modify links from first node to last node, then second node to second last node and so on
Eg: [1,2,3,4,5,6] -> [1,6,2,5,3,4]
Steps are -

1. Find mid node. (3)
2. Reverse the linked list from mid+1 to last node. (6,5,4)
3. Merge them. ([1,2,3] and [6,5,4])
   After following these steps - 1,6,2,5,3,4

Reference

#linked-list