每日一题之排序的循环链表.md

米洛 2022/6/19 leetcode

# 每日一题

大家好，我是打卡君。和我一起坚持打卡，保持大脑清醒。

# 先看题目

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
"""

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':

1
2
3
4
5
6
7
8
9
10

简单解释一下题目（其实配合图片看更好理解）：

有一个循环的链表，他们可以从某个节点开始，保持升序，现在需要你往这个链表里面插入一个节点，并按照链表的规则保持住升序。

Leetcode最大的好处就是，用例是真的丰富，根据不同的输入它已经计算好了正确的输出，可能有时候你会觉得自己做的没毛病，但其实某个case会不经意间击溃你，比如我:

也难怪这题通过率十分惨淡。

# 思路

我们无非是要插入一个节点到链表，那如果每次都能精准地找到要插入的位置，不就行啦？没错，思路是这样，不过真写起来还是稍显复杂，原因有很多，接着我们来一一过目一下，我先按最初的思路写点代码。

如果head是空，那直接插入，并返回
不为空，那我们找到他应该在的位置，比如 1234,插入4，那么他的位置就在4之前，3之后，也可以在4之后。为了统一，我们都往前插。


class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        # 1. 如果head是None，那么我们直接插入节点，并把next赋值给自己，这样就是个循环链表了
        if head is None:
            temp = Node(insertVal)
            temp.next = temp
            return temp
        # 2. 否则我们找到辣个节点，但我们需要一个前置节点，因为要往前插入
        current = head
        pre = Node(float("inf"), current) # 可以保证插入值永远小于pre.val
        while not (pre.val <= insertVal <= current.val):
            # 此时说明没找到节点，pre和current都往后挪1个节点
            pre = current
            current = current.next
            if current == head:
                # 因为是循环链表，怕产生死循环，所以遇到current == head的时候说明循环了一遍了，直接退出循环
                break
        # 中间插入一个节点
        pre.next = Node(insertVal)
        pre.next.next = current
        return head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

先来看看这种思路，这是理想情况，也就是要插入的数据刚好在这个链表范围内，也就是说链表数据范围如果是1-10的话，那么插入的数据就在1-10之间，看看上面的代码，想一下如果遇到0，或者12，是不是就寄了。

没错，我就这么寄了。

# 继续改造

这个很明显，我们需要做一层额外处理，如果循环完了还没找到对应的数，说明数字要么比所有的还小，要么比所有的还大，所以我们设置2个变量: min_val和max_val，当循环结束以后，如果当前数字等于min_val的话，那说明就是他了，在他前面插入，如果数字大于max_val，那需要把current和pre再后移一位，然后在他们前面插入这个节点。

比如: [1,2,3,4], 插入0，那应该在1的前面插入0，变成[0,1,2,3,4]

如果是[1,2,3,4], 插入5，那其实是在4的后面插入5，所以走到4,4等于最大值，并且循环已经结束过了，那4走到后面1位，也就是节点1，再到1前面插入才是合理的。

再来看看代码二:

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if head is None:
            temp = Node(insertVal)
            temp.next = temp
            return temp
        current = head
        pre = Node(float("inf"), current)
        # 是否没找到，默认是False，我们希望一开始就能找到，找不到就把他变为True
        not_found = False
        # 以第一个节点为最大 最小值
        min_val, max_val = current.val, current.val
        while not (pre.val <= insertVal <= current.val):
            if not_found:
                # 这已经是转了一圈以后了，还没找到~！那看是最小值，并且最小值要等于当前节点的值，就说明找到了
                if insertVal < min_val and current.val == min_val:
                    break
                # 也是类似上面，但是最大值有个不同，需要把current往后再挪1位
                if insertVal > max_val and current.val == max_val:
                    pre = current
                    current = current.next
                    break
            # 说明没找到
            pre = current
            current = current.next
            min_val = min(min_val, current.val)
            max_val = max(max_val, current.val)
            if current == head:
                # 已经循环起来了，直接把没找到设置为真
                not_found = True
        # 最后的插入工作，前面都是为了他准备
        pre.next = Node(insertVal)
        pre.next.next = current
        return head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

一运行，击败104个case，倒在了case105上，我们来看看具体的case:

仔细观察下，就会发现一个问题：

循环第一遍的时候:

min_val = 1 max_val = 3

然后进入第二遍循环，走到[1, 3, 3] 第一个3的时候，因为3等于最大值，所以认为应该右移一位，到最后一个3，接着插入数据，这样就变成了:

[1,3,4,3]

其实问题的关键就是因为有多个重复的最大值，所以我们找最大值，还得找到最后一个最大值，找最小值，也得找到最后一个最小值。

# 事不过三，最后一遍

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if head is None:
            temp = Node(insertVal)
            temp.next = temp
            return temp
        current = head
        pre = Node(float("inf"), current)
        not_found = False
        min_val, max_val = current, current
        while not (pre.val <= insertVal <= current.val):
            if not_found:
                # 注意这里是重点，我们min_val不存储具体的值了，存储节点，并且最大值记录的就是节点
                if insertVal < min_val.val and current == min_val:
                    break
                if insertVal > max_val.val and current == max_val:
                    pre = current
                    current = current.next
                    break
            # 说明没找到
            pre = current
            current = current.next
            # 这里加了一个not_found的判断，这样当第二遍循环的时候，到3的时候，就不会改变max_val和min_val了，投机取巧了一把
            if current.val >= max_val.val and not not_found:
                max_val = current
            if current.val <= min_val.val and not not_found:
                min_val = current
            if current == head:
                not_found = True
        pre.next = Node(insertVal)
        pre.next.next = current
        return head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

上面就是最终版本了，不得不说，测试用例真的很重要！！！写的越多，对自己的代码就越放心。

米洛的小窝

Choose mode