题目:
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:
输入:head = [], val = 1
输出:[]
示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]
//ListNode 节点 class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } //这个是int列表转ListNode节点,在网上找不到, //本地测试时候需要使用,自己写的小工具的ヾ(≧▽≦*)o public static ListNode arrayToListNode(int[] a){ ListNode head=new ListNode(a[0]); ListNode temp; temp = head; for (int i = 1; i < a.length; i++) { ListNode a1 = new ListNode(a[i]); temp.next = a1; temp = a1; } return head; }
能否写出:能写出来
时间:大概20分钟
思路:这题算是链表的入门题。必须学会,这个是我第一次写的,解答失败,在示例三里失败
测试用例:[7,7,7,7]
7
测试结果:[7,7]
期望结果:[]
原因:
我的代码里在删除元素时出现一个问题。当 head.val == val 时,只更新了 prev 的 next 指针,但没有更新 head 的值。这可能导致在下一次迭代时,如果下一个节点的值仍然等于 val,则会出现错误。
调整后正确解法
时间复杂度:O(n)
空间复杂度:O(1)