Skip to main content

Two Pointers

Single Linked List​

61. Rotate List​

Medium·
Solutions:
FIG. ROTATE LIST● INTERACTIVE
Visualize
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·
Solutions:
FIG. KTH FROM END OF LINKED LIST● INTERACTIVE
Visualize
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·
Solutions:
FIG. FIND THE SUM OF LAST N NODES OF THE LINK● INTERACTIVE
Visualize
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·
Solutions:
FIG. REMOVE NTH NODE FROM END OF LIST● INTERACTIVE
Visualize
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·
Solutions:
FIG. PLUS ONE LINKED LIST● INTERACTIVE
Visualize
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·
Solutions:
FIG. REMOVE DUPLICATES FROM SORTED LIST II● INTERACTIVE
Visualize
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·
Solutions:
FIG. MIDDLE OF THE LINKED LIST 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. DELETE THE MIDDLE NODE OF A LINKED LIST 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. INSERT IN MIDDLE OF LINKED LIST● INTERACTIVE
Visualize
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​

Solutions:
FIG. LINKED LIST CYCLE 2● INTERACTIVE
Visualize
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​

Solutions:
FIG. LINKED LIST CYCLE II 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. FIND LENGTH OF LOOP 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. REMOVE LOOP IN LINKED LIST 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. IDENTICAL LINKED LISTS● INTERACTIVE
Visualize
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·
Solutions:
FIG. ADD TWO NUMBERS 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. MERGE TWO SORTED LISTS● INTERACTIVE
Visualize
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·
Solutions:
FIG. ADD TWO POLYNOMIALS REPRESENTED AS LINKE● INTERACTIVE
Visualize
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​

Solutions:
FIG. INTERSECTION OF TWO LINKED LISTS 2● INTERACTIVE
Visualize
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·
Solutions:
FIG. INSERT INTO A SORTED CIRCULAR LINKED LIS● INTERACTIVE
Visualize
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