LeetCode题目-20250826

1. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路：

初步思路就是逐个读取一个链表的数据，然后插入另一个链表。不过链表的插入操作似乎是O(n)，另一个需要遍历，大概是O(n*m)。进一步考虑就是同步遍历，构建新链表，因为两个链表都是非递减顺序排列，从头开始往后遍历，遇到小的就把其中一个链表数据放入新链表。这样应该就是O(n+m)。

遇到问题：

个人想法是顺着两个旧链表往后找，对比大小，将小的那个放入一个新的链表。然而看了 list1：ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}结构后，给我干懵了，循环放入新链表似乎成了一个嵌套循环，next更新变得很复杂，写了半天没写出来。

GPT解法：

世界上莫大的悲哀就是，GPT一秒干出来你半小时没想起来的代码，然后你还发现自己不懂……只能进一步请教GPT。GPT按照我的逻辑实现的，不过没有新建链表，整体代码更简洁高效。首先定义一个空节点做头，避免了首个节点的判断问题。然后后续就是遍历节点，next不断往后走。current.next = list1，current = current.next这两句保证了current不断地往后更新。

我大概明白那儿不对了，我是按照类似于字典的那种思路来的，所以下一个节点的更新变得很复杂，需要不断创建新的值……其实还是链表理解不到位。MLGB，我就不信了，等下再找个链表题做做。

实现：

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()          # 建一个“哑元”头结点；val 默认是 0，但不会被返回
        current = dummy             # current 指向“已合并链表”的尾巴，一开始等于 dummy

        # 只要两个指针都没走到头，就每次接上更小（或相等）的那个节点
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1   # 把 list1 当前节点“挂”到已合并链表尾部（不拷贝值，直接连指针）
                list1 = list1.next     # list1 指针向前走
            else:
                current.next = list2   # 同理，挂 list2 的当前节点
                list2 = list2.next     # list2 指针向前走
            current = current.next      # 尾指针也跟着走到新挂上的节点

        # 跳出循环时，至少有一个链表走到头了；把剩下的整段直接接上即可
        if list1:
            current.next = list1
        else:
            current.next = list2

        return dummy.next            # 丢掉 dummy，自 dummy.next 才是合并后链表的真实头

2. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

思路：

两种思路，一个是创建一个新的链表，然后遍历旧链表，因为已经排序好了，所以找到不重复的值，往新链表里对比+放入就行。另一个就是直接遍历旧链表，遇到重复的值就删除这个节点。第二个似乎占用空间更小，看起来很简单啊。

遇到问题：

这种题目也会遇到问题？GPT实现类似逻辑，就是写法更简洁一些，不在赘述。我就知道我是天才，哈哈哈哈，再接再厉，再来一题。

实现：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution1:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head:
            num_temp = head.val
            head_rem = head
            while head.next != None:
                if head.next.val == num_temp:
                    head.next = head.next.next
                elif head.next.val != num_temp:
                    head = head.next
                    num_temp = head.val
            return head_rem
        else:
            return head
class Solution:
    # 我承认GPT的更简洁……更pythonic
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

3. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

提示：

链表中节点的数目范围是 [0, 10⁴]
-10⁵ <= Node.val <= 10⁵
pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？

思考：

感觉不难，但是似乎需要一个空间来记录next那个值，然后不断地对比是否出现重复，如果考虑O(1)内存的话……哈哈哈，其实可以疯狂循环，反正节点有数目范围，最后如果超出范围还没有None，那就是环形，内存占用肯定是O(1)，什么邪修代码哦。其实这个也没说啥破不破坏原来的链表，只是考虑是不是环形，那或许可以遍历时候，一边遍历一边设置数值为1000001啥的，如果遇到数值大于这个，那么就算环形了，不过感觉还是好蠢。算了，不管内存了，先常规方法走一遍看看吧。

GPT解法：

常规解法没毛病，GPT给了个快慢指针解法，就是一个跑得快，一个跑得慢，只要有循环，肯定能撞上这种逻辑。其实也没毛病，肯定比直接循环节点数目范围强。还有个就是哈希表解法，查找起来比常规的快，嗯，也挺好。

实现：

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

class Solution2:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        rem = []
        while head and head.next:
            rem.append(head)
            if head.next in rem:
                return True
            head = head.next
        return False

class Solution1:
    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

class Solution:
    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

1. 合并两个有序链表

2. 删除排序链表中的重复元素

3. 环形链表

发表回复 取消回复

发表回复取消回复