题解 | #删除链表峰值#

删除链表峰值

https://www.nowcoder.com/practice/30a06e4e4aa549198d85deef1bab6d25

一、知识点:

双指针、链表、遍历

二、文字分析:

算法的实现思路如下:

  1. 初始化两个指针curpre,分别指向当前节点和前一个节点。初始时,cur指向头结点的下一个节点,pre指向头结点。
  2. 使用循环遍历链表,直到当前节点cur为null。
  3. 在循环内部,使用条件判断来检查是否需要删除当前节点。
  4. 如果前一个节点的值小于当前节点的值,并且当前节点的值大于下一个节点的值(当且仅当下一个节点存在),则删除当前节点。将前一个节点的next指针指向当前节点的下一个节点,跳过当前节点。将当前节点指向下一个节点,继续下一次循环。
  5. 如果不满足删除条件,更新指针:将前一个节点指向当前节点,将当前节点指向下一个节点。
  6. 返回更新后的链表头结点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;
    }
}

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务