Linked List Traversal¶
Table of Contents¶
- 1290. Convert Binary Number in a Linked List to Integer (Easy)
- 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points (Medium)
- 2181. Merge Nodes in Between Zeros (Medium)
- 725. Split Linked List in Parts (Medium)
- 817. Linked List Components (Medium)
- 3062. Winner of the Linked List Game (Easy) 👑
- 3063. Linked List Frequency (Easy) 👑
1290. Convert Binary Number in a Linked List to Integer¶
from typing import Optional
from leetpattern.utils import ListNode
# Linked List
def getDecimalValue(head: Optional[ListNode]) -> int:
res = 0
while head:
res = res * 2 + head.val
head = head.next
return res
node = ListNode().create([1, 0, 1])
print(node) # 1 -> 0 -> 1
print(getDecimalValue(node)) # 5
2058. Find the Minimum and Maximum Number of Nodes Between Critical Points¶
from typing import List, Optional
from leetpattern.utils import ListNode
# Linked List
def nodesBetweenCriticalPoints(head: Optional[ListNode]) -> List[int]:
pre = head.val
cur = head.next
idx = 0
count = 0
res = []
mn = float("inf")
while cur.next:
idx += 1
val = cur.val
if pre > val and val < cur.next.val:
res.append(idx)
count += 1
elif pre < val and val > cur.next.val:
res.append(idx)
count += 1
if count >= 2:
mn = min(mn, res[-1] - res[-2])
pre = val
cur = cur.next
if count >= 2:
return [mn, res[-1] - res[0]]
else:
return [-1, -1]
node = ListNode().create([5, 3, 1, 2, 5, 1, 2])
print(nodesBetweenCriticalPoints(node)) # [1, 3]
2181. Merge Nodes in Between Zeros¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
def merge_nodes(head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
dummy = ListNode()
cur = dummy
head = head.next
temp = 0
while head.next:
if head.val == 0:
cur.next = ListNode(temp)
cur = cur.next
temp = 0
else:
temp += head.val
head = head.next
if temp != 0:
cur.next = ListNode(temp)
return dummy.next
def test_merge_nodes():
root = LinkedList([0, 3, 1, 0, 4, 5, 2, 0])
res = merge_nodes(root.head)
assert LinkedList(res).to_array() == [4, 11]
725. Split Linked List in Parts¶
817. Linked List Components¶
from typing import List, Optional
from leetpattern.utils import ListNode
# Linked List
def numComponents(head: Optional[ListNode], nums: List[int]) -> int:
numSet = set(nums)
res = 0
while head:
if head.val in numSet:
while head and head.val in numSet:
head = head.next
res += 1
else:
head = head.next
return res
head = ListNode().create([0, 1, 2, 3, 4])
nums = [0, 3, 1, 4]
print(numComponents(head, nums)) # 2