Skip to content

Linked List Traversal

Table of Contents

1290. Convert Binary Number in a Linked List to Integer

1290. Convert Binary Number in a Linked List to Integer - Python Solution
from typing import Optional

from template 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

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points - Python Solution
from typing import List, Optional

from template 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

2181. Merge Nodes in Between Zeros - Python Solution
from typing import Optional

from template import ListNode


# Linked List
def mergeNodes(head: Optional[ListNode]) -> Optional[ListNode]:
    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


root = ListNode.create([0, 3, 1, 0, 4, 5, 2, 0])
print(root)  # 0 -> 3 -> 1 -> 0 -> 4 -> 5 -> 2 -> 0
print(mergeNodes(root))  # 4 -> 11

725. Split Linked List in Parts

817. Linked List Components

817. Linked List Components - Python Solution
from typing import List, Optional

from template 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

3062. Winner of the Linked List Game

3063. Linked List Frequency

Comments