1. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
- 你是否可以使用
O(1)空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
提示：
- 链表中节点的数目范围在范围
[0, 10^4]内 -10^5 <= Node.val <= 10^5pos的值为-1或者链表中的一个有效索引
出处：
https://edu.csdn.net/practice/24851274
代码1： 集合元素唯一性
from typing import List class ListNode: def __init__(self, x): self.val = x self.next = None class Solution(object): def detectCycle(self, head): s = set() node = head while node is not None: if node in s: return node else: s.add(node) node = node.next return None def buildCycle(nums: List[int], pos: int) -> ListNode: if not nums: return None # 创建链表节点 nodes = [ListNode(num) for num in nums] # 创建链表 for i in range(len(nodes)-1): nodes[i].next = nodes[i+1] # 将链表尾部连接到pos处，形成环形链表 if pos != -1: nodes[-1].next = nodes[pos] return nodes[0] def printNode(node: ListNode): if node is None: print("null") else: print(node.val) # %% s = Solution() nums = [3,2,0,-4] head = buildCycle(nums, pos = 1) printNode(s.detectCycle(head)) nums = [1,2] head = buildCycle(nums, pos = 0) printNode(s.detectCycle(head)) nums = [1] head = buildCycle(nums, pos = -1) printNode(s.detectCycle(head))
输出：
2
1
null
代码2： 快慢双指针
from typing import List class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def detectCycle(self, head: ListNode) -> ListNode: slow, fast = head, head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: fast = head while slow != fast: slow = slow.next fast = fast.next return slow return None def buildCycle(nums: List[int], pos: int) -> ListNode: if not nums: return None # 创建链表节点 nodes = [ListNode(num) for num in nums] # 创建链表 for i in range(len(nodes)-1): nodes[i].next = nodes[i+1] # 将链表尾部连接到pos处，形成环形链表 if pos != -1: nodes[-1].next = nodes[pos] return nodes[0] def printNode(node: ListNode): if node is None: print("null") else: print(node.val) # %% s = Solution() nums = [3,2,0,-4] head = buildCycle(nums, pos = 1) printNode(s.detectCycle(head)) nums = [1,2] head = buildCycle(nums, pos = 0) printNode(s.detectCycle(head)) nums = [1] head = buildCycle(nums, pos = -1) printNode(s.detectCycle(head))
2. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
出处：
https://edu.csdn.net/practice/24851275
代码：
from typing import List class ListNode: def __init__(self, x): self.val = x self.next = None class Solution: def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ current = head nextNode = None h = head while current is not None and current.next is not None: nextNode = current.next if nextNode.next is not None: tmpNode = current.next current.next = nextNode.next tmpNode.next = h else: current.next = None nextNode.next = h h = nextNode return h def buildList(nums: List[int]) -> ListNode: if not nums: return None nodes = [ListNode(num) for num in nums] for i in range(len(nodes)-1): nodes[i].next = nodes[i+1] return nodes[0] def convertList(head: ListNode): ret = [] if head == None: return node = head while node != None: ret.append(node.val) node = node.next return ret # %% s = Solution() nums = [1,2,3,4,5] head = buildList(nums) print(convertList(s.reverseList(head))) nums = [1,2] head = buildList(nums) print(convertList(s.reverseList(head))) nums = [] head = buildList(nums) print(convertList(s.reverseList(head)))
输出：
[5, 4, 3, 2, 1]
[2, 1]
None
递归法：
```python class Solution: def reverseList(self, head): if head is None or head.next is None: return head newHead = self.reverseList(head.next) head.next.next = head head.next = None return newHead ···
3. 子集 II
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
1 <= nums.length <= 10
-10 <= nums[i] <= 10
出处：
https://edu.csdn.net/practice/24851276
代码：
class Solution(object): def subsetsWithDup(self, nums): nums.sort() res = [[]] begin = 0 for index in range(len(nums)): if index == 0 or nums[index] != nums[index - 1]: begin = 0 size = len(res) for j in range(begin, size): curr = list(res[j]) curr.append(nums[index]) res.append(curr) begin = size return res # %% s = Solution() print(s.subsetsWithDup(nums = [1,2,2]))
输出：
[[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]
