Skip to main content

Two Pointers

Single Linked List​

61. Rotate List​

61. Rotate List

Medium1 solution1 playground
Solutions:

Watch the two panels: head (top) shrinks to the first n − k nodes once left.next = None runs, and sentinel (bottom) grows as sentinel.next = left.next then right.next = head is rewired — by the last step sentinel is the rotated list. The legacy view depicted this as a Y-fork; the two-panel layout makes the rewire equally readable.

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​

Kth from End of Linked List

Easy1 solution1 playground
Solutions:

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​

Easy1 solution1 playground
Solutions:
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​

19. Remove Nth Node From End of List

Medium2 solutions2 playgrounds
Solutions:

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​

369. Plus One Linked List

Medium2 solutions2 playgrounds
Solutions:

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​

Medium1 solution1 playground

Solutions:
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​

876. Middle of the Linked List

Easy3 solutions1 playground
Solutions:
def middleNode(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow

2095. Delete the Middle Node of a Linked List​

Medium3 solutions1 playground
Solutions:
def deleteMiddle(head):
if not head or not head.next:
return None
slow = fast = head
prev = slow
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = prev.next.next
return head

Insert in Middle of Linked List​

Insert in Middle of Linked List

Basic1 solution1 playground
Solutions:

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​

141. Linked List Cycle

Easy2 solutionsexplanation1 playground
Solutions:
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False

142. Linked List Cycle II​

142. Linked List Cycle II

Medium2 solutionsexplanation1 playground
Solutions:
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
while head != slow:
head = head.next
slow = slow.next
return head
return None

Find length of Loop​

Find length of Loop

Easy2 solutions1 playground
Solutions:
def countNodesInLoop(head):
slow = fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
count = 1
slow = slow.next
while slow != fast:
slow = slow.next
count += 1
return count
return 0

Remove loop in Linked List​

Remove loop in Linked List

Medium2 solutions1 playground
Solutions:
def removeLoop(head):
prev = None
slow = fast = head
while fast and fast.next:
fast = fast.next.next
prev = slow
slow = slow.next
if fast == slow:
front = head
while front != slow:
prev = slow
slow, front = slow.next, front.next
prev.next = None
return True

Two Linked Lists​

Identical Linked Lists​

Identical Linked Lists

Basic1 solution1 playground
Solutions:

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​

2. Add Two Numbers

Medium2 solutions1 playground
Solutions:
def addTwoNumbers(l1, l2):
sentinel = s = ListNode(None)
x, y = l1, l2
carry = 0
while x or y or carry:
x_val, y_val = x.val if x else 0, y.val if y else 0
carry, rem = divmod(x_val + y_val + carry, 10)
s.next = s = ListNode(rem)
x, y = x.next if x else None, y.next if y else None
return sentinel.next

21. Merge Two Sorted Lists​

21. Merge Two Sorted Lists

Easy2 solutions1 playground
Solutions:

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​

Medium1 solution1 playground
Solutions:

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​

160. Intersection of Two Linked Lists

Solutions:
def getIntersectionNode(headA, headB):
x, y = headA, headB
while x != y:
print(x.val if x else None, y.val if y else None)
x = x.next if x else headB
y = y.next if y else headA
return x

Circular Linked Lists​

708. Insert into a Sorted Circular Linked List​

Medium1 solution1 playground
Solutions:

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