Skip to main content

Three Pointers

206. Reverse Linked List​

2 Approachesclick to switch
FIG. REVERSE LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • front walks the list once, n being the number of nodes.
Space
O(1)
  • Only front, mid, and back are kept, regardless of list length.
def reverseList(head):
"""Abdul Bari's solution"""
front, mid, back = head, None, None
while front:
front, mid, back = front.next, front, mid
mid.next = back
return mid

Reverse a Doubly Linked List​

Easy·
2 Approachesclick to switch
FIG. REVERSE A DOUBLY LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • front walks forward through each of the n nodes exactly once.
Space
O(1)
  • Only front, mid, and back are tracked, regardless of n.
def reverseDLL(head):
front, mid, back = head, None, None
while front:
front, mid, back = front.next, front, mid
mid.next = back
mid.prev = front
return mid

Reverse both parts​

Easy·
FIG. REVERSE BOTH PARTS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • front walks every one of the n nodes in the list exactly once, rewiring .next pointers in place.
Space
O(1)
  • Only a fixed set of pointer variables (front, mid, back, new_head, sep, tail) are tracked, independent of the list's length.
def reverse(head, k):
sep = tail = new_head = None
index = 0
front, mid, back = head, None, None
while front:
if not front.next:
tail = front
if index == k - 1:
new_head = front
if index == k:
sep = front
front, mid, back = front.next, front, mid
mid.next = back
index += 1
 
head.next = tail
sep.next = None
return new_head

24. Swap Nodes in Pairs​

Medium·
3 Approachesclick to switch
FIG. SWAP NODES IN PAIRS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes - the while front loop advances back, mid, and front two nodes at a time, visiting each node once.
Space
O(1)
  • Only the sentinel node and the three pointers front, mid, back are allocated, regardless of list length.
def swapPairs(head):
if not head or not head.next:
return head
sentinel = ListNode(None, next=head)
front, mid, back = head.next, head, sentinel
while front:
mid.next = front.next
front.next = mid
back.next = front
 
back = mid
mid = mid.next
front = mid.next if mid else None
return sentinel.next