Two Pointers
Single Linked List
61. Rotate List
Medium61. Rotate List
- Solution
Interactive Visualization
- Python
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
- Solution
- Python
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
Find the Sum of Last N nodes of the Linked List
- Solution
- Python
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 totals
19. Remove Nth Node From End of List
- Two Pass
- One Pass
Interactive Visualization
- Python
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
Interactive Visualization
- Python
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
sentinel = ListNode(None, next=head)
right = sentinel
for _ in range(n):
right = right.next
left = sentinel
while right.next:
left = left.next
right = right.next
left.next = left.next.next
return sentinel.next
369. Plus One Linked List
- Iterative
- Recursive
Interactive Visualization
- Python
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
Interactive Visualization
- Python
def plusOne(self, head: ListNode) -> ListNode:
def recursion(node):
if not node:
return 1
carry = recursion(node.next)
carry, node.val = divmod(node.val + carry, 10)
return carry
if recursion(head):
new_node = ListNode(1, next=head)
return new_node
return head
82. Remove Duplicates from Sorted List II
Interactive Visualization
- Sentinel + Predecessor
- Python
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
::::
- Two Pass
- One Pass: Slow & Fast
- Python
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
def getLen(head):
length = 0
while head:
length += 1
head = head.next
return length
mid = getLen(head) // 2
curr = head
for _ in range(mid):
curr = curr.next
return curr
Interactive Visualization
- Python
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
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
- Array conversion
- Two Pass
- One Pass: Slow & Fast
- Python
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
- Python
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
def getLen(head):
length = 0
while head:
length += 1
head = head.next
return length
if not head or not head.next:
return None
mid = getLen(head) // 2 - 1
curr = head
for _ in range(mid):
curr = curr.next
curr.next = curr.next.next
return head
- Python
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
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
- One Pass: Slow & Fast
- Python
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
- Hash Set
- Floyd's Cycle Finding
- Python
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
Interactive Visualization
Explanation
- Python
def hasCycle(self, head: Optional[ListNode]) -> bool:
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
- Hash Set
- Floyd's Tortoise and Hare
- Python
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
Interactive Visualization
Explanation
- Python
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
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
- Hash Set
- Floyd's Tortoise and Hare
- Python
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
- Python
def countNodesInLoop(self, 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
- Hash Set
- Floyd's Tortoise and Hare
- Python
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
- Python
def removeLoop(self, 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
- Solution
- Python
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. Add Two Numbers
- In Place
- New LL
- Python
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
- Python
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
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
- Iterative
- Recursive
- Python
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
- Python
def mergeTwoLists(
self, list1: Optional[ListNode], list2: Optional[ListNode]
) -> Optional[ListNode]:
def recursion(a, b):
if a and b:
if a.val <= b.val:
a.next = recursion(a.next, b)
return a
else:
b.next = recursion(a, b.next)
return b
return a if a else b
return recursion(list1, list2)
1634. Add Two Polynomials Represented as Linked Lists
- Solution
- Python
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
- Brute Force
- Hash Set
- Length Difference
- Two Pointers
- Python
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
- Python
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
seen = set()
while headA:
seen.add(headA)
headA = headA.next
while headB:
if headB in seen:
return headB
headB = headB.next
return None
- Python
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
len1 = getLen(headA)
len2 = getLen(headB)
if len1 < len2:
headA, headB = headB, headA
len1, len2 = len2, len1
x, y = headA, headB
for _ in range(len1 - len2):
x = x.next
while x and y:
if x == y:
return x
x, y = x.next, y.next
return None
Interactive Visualization
- Python
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
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
- Solution
Interactive Visualization
- Python
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