题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个链表，对于其中的每一个节点，如果其右侧有比该节点值更大的点，就删除该点，求最后的链表。

思路分享

  • 朴素解法：先遍历一次链表，把节点的值转化成数组，然后再求每个下标的右边的最大值，再遍历一次链表，这次对于值小于对应右侧最大值的就删除。时间 O(3n)

  • 灵神给出了更优雅的解法，下面就说下递归的。递归天然就适合倒着来，毕竟链表比较右侧数值正好就是倒着的。可以从最后的两个点开始模拟，最后一个点自然是直接返回，所以递归函数的含义是获取该节点及之后数值最大的那个节点，如果当前节点比这个小，那就可以删掉当前节点，直接返回最大节点；反之则让当前节点与获得点相连，然后返回。

    https://leetcode.cn/problems/remove-nodes-from-linked-list/solutions/1993491/di-gui-jian-ji-xie-fa-by-endlesscheng-jfwi/

代码解答（强烈建议自行解答后再看）

  • 参考题解
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
35
36
37
38
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归
        if not head.next:
            return head 
        node = self.removeNodes(head.next)
        if head.val < node.val:
            return node
        head.next = node
        return head

        # O(3n)
        rec = []
        cur = head
        while cur:
            rec.append(cur.val)
            cur = cur.next
        
        for i in range(len(rec)-2, -1, -1):
            rec[i] = max(rec[i], rec[i+1])
        
        index = 0
        ans = ListNode(0, head)
        cur = ans
        # print(rec)
        while cur.next:
            if cur.next.val < rec[index]:
                cur.next = cur.next.next
            else:
                cur = cur.next
            index += 1
            
        return ans.next