题解 | #删除链表峰值#
删除链表峰值
https://www.nowcoder.com/practice/30a06e4e4aa549198d85deef1bab6d25
题目考察的知识点:链表、链表节点操作、基本算法思想(遍历和删除节点)。
题目解答方法的文字分析:这道题目给定了一个链表,表示农场主人养的一群牛,每只牛都有一个编号。我们需要在链表中删除那些编号比前后节点值都大的牛。注意,链表的首尾节点不参与删除操作。
为了解决这个问题,我们可以使用遍历链表的方法来检查每个节点的值是否满足删除条件。首先,我们定义一个辅助节点作为链表的头节点,并将其值设置为一个较大的值,以确保它不会被删除。然后,我们从头节点开始遍历链表,检查每个节点的值是否满足删除条件:当前节点值大于前一个节点的值且大于后一个节点的值。如果满足删除条件,我们就将当前节点从链表中移除,否则继续遍历下一个节点。最后,我们返回链表的头节点的下一个节点作为结果。
本题解析所用的编程语言:Java
完整且正确的编程代码如下:
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode deleteNodes (ListNode head) { if (head == null || head.next == null) { return head; } ListNode dummy = new ListNode(Integer.MAX_VALUE); dummy.next = head; ListNode prev = dummy; ListNode curr = head; while (curr != null && curr.next != null) { if (curr.val > prev.val && curr.val > curr.next.val) { prev.next = curr.next; } else { prev = curr; } curr = curr.next; } return dummy.next; } }