Skip to main content

Two Pointers

Single Linked List​

61. Rotate List​

Medium·
FIG. ROTATE LIST● INTERACTIVE
visualization loads as you reach it
Time
O(2n)
  • getLen(head) walks the whole list once: O(n), where n is the number of nodes.
  • The for _ in range(k) loop advances right at most n times (since k is reduced mod n), then the while right and right.next loop advances left/right together at most n more times: O(n).
  • Total across both passes: O(2n).
Space
O(1)
  • Only sentinel, left, right, and k are tracked; no structure grows with n.
def getLen(head):
length = 0
while head:
head = head.next
length += 1
return length
 
 
def rotateRight(head, k):
if not head:
return None
k = k % getLen(head)
if not k:
return head
sentinel = ListNode(None, next=head)
right = left = head
for _ in range(k):
right = right.next if right else head
while right and right.next:
left, right = left.next, right.next
sentinel.next = left.next
left.next = None
right.next = head
return sentinel.next

Kth from End of Linked List​

Easy·
FIG. KTH FROM END OF LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • fast advances k steps, then fast and slow advance together until fast runs off the list - together they touch each node at most once, O(n).
Space
O(1)
  • Only the slow and fast pointers are tracked.
def getKthFromLast(head, k):
slow = fast = head
for _ in range(k):
if not fast:
return -1
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow.data

Find the Sum of Last N nodes of the Linked List​

Easy·
FIG. FIND THE SUM OF LAST N NODES OF THE LINK● INTERACTIVE
visualization loads as you reach it
Time
O(L + n)
  • L is the total number of nodes in the list. The for _ in range(n) loop advances fast by n nodes.
  • The while fast loop then advances both fast and slow together for the remaining L - n nodes until fast runs off the list.
  • The final while slow loop sums the last n nodes.
  • These three passes add up to n + (L - n) + n = L + n.
Space
O(1)
  • Only the pointers slow, fast and the scalar total are tracked, independent of L or n.
def sumOfLastN_Nodes(head, n):
slow = fast = head
for _ in range(n):
if not fast:
return -1
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
total = 0
while slow:
total += slow.data
slow = slow.next
return total

19. Remove Nth Node From End of List​

Medium·
2 Approachesclick to switch
FIG. REMOVE NTH NODE FROM END OF LIST● INTERACTIVE
visualization loads as you reach it
Time
O(2n)
  • One O(n) pass walks curr to the end to count length, then a second pass walks curr from sentinel up to offset steps (at most n) - 2n.
Space
O(1)
  • Only sentinel, length, offset, and curr are tracked, no extra structure sized by the list.
def removeNthFromEnd(head, n):
sentinel = ListNode(None, next=head)
length = 0
curr = head
while curr:
length += 1
curr = curr.next
offset = length - n
curr = sentinel
for _ in range(offset):
curr = curr.next
curr.next = curr.next.next
return sentinel.next

369. Plus One Linked List​

Medium·
2 Approachesclick to switch
FIG. PLUS ONE LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(2n)
  • n = number of nodes in head. The first while curr scan walks every node once to find rightmost_non9 - O(n). The second while curr scan zeroes out every node after it - also O(n) in the worst case (all nines). Two separate passes give 2n.
Space
O(1)
  • Only the sentinel, curr, and rightmost_non9 pointers are kept; nothing scales with n.
def plusOne(head):
sentinel = ListNode(0, next=head)
curr = sentinel
rightmost_non9 = curr
while curr:
if curr.val != 9:
rightmost_non9 = curr
curr = curr.next
rightmost_non9.val += 1
curr = rightmost_non9.next
while curr:
curr.val = 0
curr = curr.next
return sentinel if sentinel.val else head

82. Remove Duplicates from Sorted List II​

Medium·
FIG. REMOVE DUPLICATES FROM SORTED LIST II● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • curr only ever moves forward (including inside the inner while that skips a duplicate run), visiting each of the n nodes exactly once.
Space
O(1)
  • Only sentinel, prev, and curr are tracked, regardless of n.
def deleteDuplicates(head):
sentinel = ListNode(None, next=head)
curr = sentinel
prev = sentinel
while curr:
if curr.next and curr.val == curr.next.val:
while curr and curr.next and curr.val == curr.next.val:
curr = curr.next
curr = curr.next
prev.next = curr
else:
prev = curr
curr = curr.next
return sentinel.next

Slow & Fast Pointers​

876. Middle of the Linked List​

Easy·
3 Approachesclick to switch
FIG. MIDDLE OF THE LINKED LIST 2● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while head loop walks every one of the n nodes once to fill arr.
Space
O(n)
  • arr stores a reference to all n nodes.
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
arr = []
while head:
arr.append(head)
head = head.next
return arr[len(arr) // 2]

2095. Delete the Middle Node of a Linked List​

Medium·
3 Approachesclick to switch
FIG. DELETE THE MIDDLE NODE OF A LINKED LIST 2● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while curr loop walks every node once to fill arr.
Space
O(n)
  • arr stores a reference to every one of the n nodes.
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
arr = []
curr = head
while curr:
arr.append(curr)
curr = curr.next
prev = arr[len(arr) // 2 - 1]
prev.next = prev.next.next
return head

Insert in Middle of Linked List​

Basic·
FIG. INSERT IN MIDDLE OF LINKED LIST● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • slow and fast walk the list once - fast advances two steps per iteration, so the loop runs at most n / 2 times, still O(n) for n nodes.
Space
O(1)
  • Only new_node, slow, and fast are allocated; the list is spliced in place.
def insertInMiddle(head, x):
new_node = Node(data=x)
if not head:
return new_node
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
new_node.next = slow.next
slow.next = new_node
return head

141. Linked List Cycle​

2 Approachesclick to switch
FIG. LINKED LIST CYCLE 2● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • curr visits each of the n nodes at most once before either finding a repeat or reaching the end.
Space
O(n)
  • seen can grow to hold all n nodes when there is no cycle.
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
curr = head
seen = set()
while curr:
if curr in seen:
return True
seen.add(curr)
curr = curr.next
return False

142. Linked List Cycle II​

2 Approachesclick to switch
FIG. LINKED LIST CYCLE II 2● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • curr walks each of the n nodes at most once, checking membership in seen.
Space
O(n)
  • seen can grow to hold all n nodes if there is no cycle.
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
curr = head
seen = set()
while curr:
if curr in seen:
return curr
seen.add(curr)
curr = curr.next
return None

Find length of Loop​

Easy·
2 Approachesclick to switch
FIG. FIND LENGTH OF LOOP 2● INTERACTIVE
visualization loads as you reach it
Time
O(2n)
  • The first while curr loop walks the list until it revisits a node, at most n nodes - O(n).
  • Once a repeat is found, the inner while slow != curr loop walks back around the cycle to count its length, at most n nodes - a second O(n) pass.
Space
O(n)
  • seen holds every node visited before a repeat is found, up to all n nodes in the worst case.
class Solution:
def countNodesInLoop(self, head):
seen = set()
curr = head
while curr:
if curr in seen:
count = 1
slow = curr.next
while slow != curr:
slow = slow.next
count += 1
return count
else:
seen.add(curr)
curr = curr.next
return 0

Remove loop in Linked List​

Medium·
2 Approachesclick to switch
FIG. REMOVE LOOP IN LINKED LIST 2● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • The while curr loop visits each node exactly once via curr = curr.next, doing an O(1) set lookup/insert (curr in seen, seen.add(curr)) per node: O(n), where n is the number of nodes.
Space
O(n)
  • seen stores a reference to every visited node before the loop is found (or the list ends), up to O(n).
class Solution:
def removeLoop(self, head):
seen = set()
prev = None
curr = head
while curr:
if curr in seen:
prev.next = None
return True
else:
seen.add(curr)
prev = curr
curr = curr.next

Two Linked Lists​

Identical Linked Lists​

Basic·
FIG. IDENTICAL LINKED LISTS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the length of the shorter list - the while a and b loop advances a and b together one node at a time, stopping as soon as either list runs out.
Space
O(1)
  • Only the pointers a and b are tracked, regardless of list length.
def areIdentical(head1, head2):
a, b = head1, head2
while a and b:
if a.data != b.data:
return False
a, b = a.next, b.next
return not a and not b

2. Add Two Numbers​

Medium·
2 Approachesclick to switch
FIG. ADD TWO NUMBERS 2● INTERACTIVE
visualization loads as you reach it
Time
O(m + n)
  • The first while x and y loop advances both lists together for min(m, n) steps, where m = len(l1) and n = len(l2); whichever list is longer is then walked the rest of the way in the following while x / while y loop - together every node of both lists is visited exactly once, m + n.
Space
O(1)
  • The digits are overwritten in place on the existing nodes (x.val = y.val = rem), and only a constant number of scalars (carry, x_prev, y_prev) plus at most one extra ListNode(1) for a final carry are allocated.
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
x, y = l1, l2
carry = 0
x_prev = None
while x and y:
carry, rem = divmod(x.val + y.val + carry, 10)
x.val = y.val = rem
x_prev = x
x, y = x.next, y.next
while x:
carry, x.val = divmod(x.val + carry, 10)
x_prev = x
x = x.next
if not y:
x_prev.next = ListNode(1) if carry else None
return l1
 
y_prev = y
while y:
carry, y.val = divmod(y.val + carry, 10)
y_prev = y
y = y.next
y_prev.next = ListNode(1) if carry else None
return l2

21. Merge Two Sorted Lists​

Easy·
2 Approachesclick to switch
FIG. MERGE TWO SORTED LISTS● INTERACTIVE
visualization loads as you reach it
Time
O(m + n)
  • m = len(list1), n = len(list2). The while a and b loop advances one pointer per iteration, consuming exactly one node from list1 or list2 each time - at most m + n iterations total.
Space
O(1)
  • Only sentinel, a, b, and curr are tracked; existing nodes are relinked in place, no new nodes or structures are allocated.
def mergeTwoLists(list1, list2):
sentinel = ListNode(None)
a, b = list1, list2
curr = sentinel
while a and b:
if a.val <= b.val:
curr.next = a
curr, a = curr.next, a.next
else:
curr.next = b
curr, b = curr.next, b.next
curr.next = a if a else b
return sentinel.next

1634. Add Two Polynomials Represented as Linked Lists​

Medium·
FIG. ADD TWO POLYNOMIALS REPRESENTED AS LINKE● INTERACTIVE
visualization loads as you reach it
Time
O(m + n)
  • m and n are the lengths of poly1 and poly2.
  • The first while a and b loop advances a, b, or both by one node per iteration; the two trailing while a / while b loops drain whatever remains. Together every node of both lists is visited exactly once - m + n total steps.
Space
O(m + n)
  • Each step allocates a fresh PolyNode onto the result list via curr.next = PolyNode(...); in the worst case (no matching powers cancel to zero) that is up to m + n new nodes.
def addPoly(poly1, poly2):
sentinel = PolyNode()
curr = sentinel
a, b = poly1, poly2
while a and b:
if a.power > b.power:
curr.next = PolyNode(a.coefficient, a.power)
a, curr = a.next, curr.next
elif a.power < b.power:
curr.next = PolyNode(b.coefficient, b.power)
b, curr = b.next, curr.next
else:
total = a.coefficient + b.coefficient
if total:
curr.next = PolyNode(total, a.power)
curr = curr.next
a = a.next
b = b.next
while a:
curr.next = PolyNode(a.coefficient, a.power)
a, curr = a.next, curr.next
while b:
curr.next = PolyNode(b.coefficient, b.power)
b, curr = b.next, curr.next
return sentinel.next

Go Circular​

160. Intersection of Two Linked Lists​

4 Approachesclick to switch
FIG. INTERSECTION OF TWO LINKED LISTS 2● INTERACTIVE
visualization loads as you reach it
Time
O(m * n)
  • m = len(headA), n = len(headB). For every node of headA the inner while y walks the whole of headB looking for a match - m * n in the worst case (no intersection).
Space
O(1)
  • Only the two traversal pointers headA and y are kept; no extra structure grows with input size.
class Solution:
def getIntersectionNode(
self, headA: ListNode, headB: ListNode
) -> Optional[ListNode]:
while headA:
y = headB
while y:
if headA == y:
return headA
y = y.next
headA = headA.next
return None

Circular Linked Lists​

708. Insert into a Sorted Circular Linked List​

Medium·
FIG. INSERT INTO A SORTED CIRCULAR LINKED LIS● INTERACTIVE
visualization loads as you reach it
Time
O(n)
  • n is the number of nodes in the circular list. prev/curr walk around the list at most once (the loop breaks when prev == head again), so the search is a single O(n) pass.
Space
O(1)
  • Only new_node, prev, and curr are allocated/tracked; no structure scales with n.
def insert(head, insertVal):
new_node = ListNode(insertVal)
if not head:
new_node.next = new_node
return new_node
prev, curr = head, head.next
while not (
(prev.val <= insertVal <= curr.val)
or (prev.val > curr.val and insertVal > prev.val)
or (prev.val > curr.val and insertVal < curr.val)
):
prev, curr = prev.next, curr.next
if prev == head:
break
prev.next = new_node
new_node.next = curr
return head