一、知识点:
双指针、链表、遍历
二、文字分析:
算法的实现思路如下:
- 初始化两个指针
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;
}
}

京公网安备 11010502036488号