Skip to main content

Two Pointers

Single Linked List​

61. Rotate List

Medium1 solution1 playground

61. Rotate List​

Solutions:

Interactive Visualization

def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
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

Easy1 solution1 playground

Kth from End of Linked List​

Solutions:

Interactive Visualization

def getKthFromLast(self, 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
Easy1 solution1 playground

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

Solutions:

Interactive Visualization

def sumOfLastN_Nodes(self, 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

Medium2 solutions2 playgrounds

19. Remove Nth Node From End of List​

Solutions:

Interactive Visualization

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
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

Medium2 solutions2 playgrounds

369. Plus One Linked List​

Solutions:

Interactive Visualization

def plusOne(self, head: ListNode) -> ListNode:
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
Medium1 solution1 playground

82. Remove Duplicates from Sorted List II​

Interactive Visualization

Solutions:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
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

Easy3 solutions1 playground

876. Middle of the Linked List​

Solutions:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
arr = []
while head:
arr.append(head)
head = head.next
return arr[len(arr) // 2]
Medium3 solutions1 playground

2095. Delete the Middle Node of a Linked List​

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

Basic1 solution1 playground

Insert in Middle of Linked List​

Solutions:

Interactive Visualization

def insertInMiddle(self, 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

Easy2 solutionsexplanation1 playground

141. Linked List Cycle​

Solutions:
def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False

142. Linked List Cycle II

Medium2 solutionsexplanation1 playground

142. Linked List Cycle II​

Solutions:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
seen = set()
while head:
if head in seen:
return head
seen.add(head)
head = head.next
return None

Find length of Loop

Easy2 solutions1 playground

Find length of Loop​

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

Medium2 solutions1 playground

Remove loop in Linked List​

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

Basic1 solution1 playground

Identical Linked Lists​

Solutions:

Interactive Visualization

def areIdentical(self, 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

Medium2 solutions1 playground

2. Add Two Numbers​

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

Easy2 solutions1 playground

21. Merge Two Sorted Lists​

Solutions:

Interactive Visualization

def mergeTwoLists(
self, list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
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
Medium1 solution1 playground

1634. Add Two Polynomials Represented as Linked Lists​

Solutions:

Interactive Visualization

def addPoly(self, poly1: "PolyNode", poly2: "PolyNode") -> "PolyNode":
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(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​

Medium1 solution1 playground

708. Insert into a Sorted Circular Linked List​

Solutions:

Interactive Visualization

def insert(self, head: "Optional[Node]", insertVal: int) -> "Node":
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