1、算法思路
讲一下设置虚拟头节点的那个方法,设置一个新节点指向原来链表的头节点,这样我们就可以通过判断链表的当前节点的后继节点值是不是目标删除值,来判断是否删除这个后继节点了。如果不设置虚拟头节点,则需要将头节点和后面的节点分开来讨论,代码会复杂一点。
2、Java代码实现
package listnodes;
//Definition for singly-linked list.
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class RemoveElements {
public static void main(String[] args) {
//构造链表
// int[] nums = new int[]{1,2,6,3,4,5,6};
// int[] nums = new int[]{7,7,7,7};
int[] nums = new int[]{1,2,2,1};
ListNode head = null;
for (int i = nums.length - 1; i >= 0; i--) {
ListNode node = new ListNode(nums[i]);
if(head != null){
node.next = head;
}
head = node;
}
//处理链表
Solution sol = new Solution();
// ListNode resNode = sol.removeElements(head, 6);//[1,2,3,4,5]
// ListNode resNode = sol.removeElements(head, 7);//[]
ListNode resNode = sol.removeElements(head, 2);//[1, 1]
//遍历链表并打印
StringBuilder sb = new StringBuilder("[");
while(resNode != null){
if(sb.length() != 1) sb.append(", ");
sb.append(resNode.val);
resNode = resNode.next;
}
sb.append("]");
System.out.println(sb);
}
}
// 递归法
//class Solution {
// public ListNode removeElements(ListNode head, int val) {
// if (head == null) {
// return head;
// }
// head.next = removeElements(head.next, val);
// return head.val == val ? head.next : head;
// }
//}
// 头结点是否删除最后再考虑
//class Solution {
// public ListNode removeElements(ListNode head, int val) {
// ListNode pre = head;
// while(pre != null && pre.next != null){
// if(pre.next.val == val){
// //跳过当前节点的后一个节点赋值给当前节点的前一个节点的next,相当于删除当前节点
// pre.next = pre.next.next;
// }else{
// pre = pre.next;
// }
// }
// pre = head;
// while(pre != null && pre.val == val){
// pre = pre.next;
// }
// return pre;
// }
//}
// 设置一个虚拟头结点,这样代码更简单
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode temp = new ListNode(0);
temp.next = head;
ListNode pre = temp;
while(pre.next != null){
if(pre.next.val == val){
//跳过当前节点的后一个节点赋值给当前节点的前一个节点的next,相当于删除当前节点
pre.next = pre.next.next;
}else{
pre = pre.next;
}
}
return temp.next;
}
}
3、完整题目
203. 移除链表元素
给你一个链表的头节点 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:文章来源:https://www.toymoban.com/news/detail-744809.html
输入:head = [7,7,7,7], val = 7 输出:[]
提示:文章来源地址https://www.toymoban.com/news/detail-744809.html
- 列表中的节点数目在范围
[0, 10^4]
内 1 <= Node.val <= 50
0 <= val <= 50
到了这里,关于算法题:203. 移除链表元素(递归法、设置虚拟头节点法等3种方法)Java实现创建链表与解析链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!