Leetcode【817、876、1019】

问题描述：【Hash Table】817. Linked List Components

解题思路：

这道题是给一个链表和数组，数组是链表元素的子集。求数组中联通数量。

直接将数组转化为集合，然后遍历一次链表。令 ans = 0，flag = True：

• 如果 flag = True 并且链表元素在集合中，则 ans 加 1，同时设置标记 flag = False；
• 如果链表元素不在集合中时，设置 flag = True；
• 最后 ans 就是答案。

时间复杂度和空间复杂度均为 O(n)。

Python3 实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def numComponents(self, head: ListNode, G: List[int]) -> int:
        ans, flag = 0, True
        G = set(G)
        cur = head
        while cur:
            if flag and cur.val in G:  # 找到一个新的联通量
                ans += 1
                flag = False
            elif cur.val not in G:
                flag = True
            cur = cur.next
        return ans

---

问题描述：【Two Pointers】876. Middle of the Linked List

解题思路：

求链表中间的结点，如果链表长度为偶数，返回中间的第二个结点。

很明显，使用快慢指针（1步和2步），遍历链表一次就可以找到。

Python3 实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

---

问题描述：【Stack】1019. Next Greater Node In Linked List

解题思路：

这道题是给一个链表，返回一个列表，列表的对应位置是链表中当前结点的下一个更大的结点的值。

这道题和 Leetcode 【Stack】739. Daily Temperatures 思路相同。都是维护一个递减栈即可。只不过 Leetcode 739 需要求温度间隔，这道题求下一个更大结点的值。

因为是链表，所以栈中需要保存结点的值和对应索引。时间复杂度和空间复杂度均为 O(n)。

Python3 实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        ans, stack = [], []
        cur = head
        size = 0  # 链表元素索引
        while cur:
            ans.append(0)  # 每次增加一个位置，这样只需要一次链表循环
            while stack and stack[-1][0] < cur.val:
                tmp = stack.pop()
                ans[tmp[1]] = cur.val
            stack.append([cur.val, size])  # 判断完后入栈
            size += 1
            cur = cur.next
        return ans