一、知识点:
双指针、链表、遍历
二、文字分析:
算法的实现思路如下:
- 初始化两个指针
cur
和pre
,分别指向当前节点和前一个节点。初始时,cur
指向头结点的下一个节点,pre
指向头结点。 - 使用循环遍历链表,直到当前节点
cur
为null。 - 在循环内部,使用条件判断来检查是否需要删除当前节点。
- 如果前一个节点的值小于当前节点的值,并且当前节点的值大于下一个节点的值(当且仅当下一个节点存在),则删除当前节点。将前一个节点的next指针指向当前节点的下一个节点,跳过当前节点。将当前节点指向下一个节点,继续下一次循环。
- 如果不满足删除条件,更新指针:将前一个节点指向当前节点,将当前节点指向下一个节点。
- 返回更新后的链表头结点
head
。
该算法通过遍历链表一次来删除递减子序列节点。时间复杂度为O(n),其中n是链表的长度。空间复杂度为O(1),使用了固定数量的额外指针来完成操作。
三、编程语言:
java
四、正确代码:
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param head ListNode类 * @return ListNode类 */ public ListNode deleteNodes(ListNode head) { ListNode cur = head.next; // 当前节点指针 ListNode pre = head; // 前一个节点指针 while (cur != null) { // 如果前一个节点的值小于当前节点的值, // 且当前节点的值大于下一个节点的值(存在下一个节点), // 则删除当前节点 if (pre.val < cur.val && cur.next != null && cur.val > cur.next.val) { pre.next = cur.next; cur = cur.next; } else { pre = cur; cur = cur.next; } } return head; } }