题解 | #删除链表峰值#
删除链表峰值
https://www.nowcoder.com/practice/30a06e4e4aa549198d85deef1bab6d25
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) { // write code here if (head == null || head.next == null) { return head; // 链表为空或只有一个节点,不需要删除 } // 记录temp前驱结点 ListNode temp = head; // cur相当于当前节点 ListNode cur = head; // cur向后走一步,相当于走到第二个结点,而temp相当于在第一个结点 cur = cur.next; while(cur.next!=null){ // 判断是否为峰值情况,如果是,直接跳过当前节点,让前驱结点指向当前节点的下一个节点即可 if(cur.val>temp.val&&cur.val>cur.next.val){ temp.next = cur.next; } //前驱结点向后走一步 temp = cur; // 当前节点向后走一步 cur = cur.next; } // 返回头结点即可,因为temp和cur都已经进行向后遍历,不能再使用 return head; } }
知识点:
- 链表:了解链表的基本概念,以及单向链表的节点结构。
- 遍历:能够使用循环或递归来遍历链表的所有节点。
- 条件判断:能够判断节点是否满足删除条件。
题目解答方法:
一种简单的方法是,从链表的第二个节点开始遍历到倒数第二个节点,对于每个节点,判断它是否比前后的节点都大。如果是,则删除该节点。删除操作可以通过调整前一个节点的指针来实现。