题目
Leetcode203题:移除链表元素
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
1,一般方法
先判断头节点,若不是,向后寻找val节点,找到待删除节点前驱,再删除val节点
public ListNode removeElements(ListNode head, int val) {
//判断头节点是否是空,且头节点正好是待删除的节点节点
while(head != null && head.val == val){
ListNode node = head;
head = head.next;
head.next = null;
}
if(head == null){
return null;//链表为空
}else{
//从头寻找val节点
ListNode prev = head;
while(prev != null){
if(prev.val == val){
//prev 是待删除节点前驱
//node就是待删除节点
ListNode node = prev.next;
prev.next = node.next;
node.next = null;
}else{
prev = prev.next;
}
}
return head;
}
2,虚拟头节点法
单链表插入,删除都需要考虑头节点,当寻找前驱节点时由于头节点不存在前驱节点,需要另外考虑,此时引入虚拟头节点dummyHead,虚拟头节点不存储具体元素,不考虑头结点是否空,头节点一定存在,则所有节点都有前驱节点
public ListNode removeElements(ListNode head, int val) {
ListNode dummyHead = new ListNode(-1);//虚拟头节点
//和链表链接
dummyHead.next = head;
ListNode prev = dummyHead;
//虚拟头节点prev不存储具体元素,从虚拟头节点下一节点开始看
while(prev.next != null){
if(prev.next.val == val){
//node就是待删除的节点
ListNode node = prev.next;
prev.next = node.next;
node.next = null;//删除
}else{
//此时prev不是待删除节点的前驱,向后移动
prev =prev.next;
}
}
return dummyHead.next;
}
3,递归法
使用递归的情况
(1)一个大问题分成若干小问题
(2)大问题和子问题规模相同,求解思路相同
(3)存在递归终止条件
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return null;
}
//删除头节点之后的元素
head.next = removeElements(head.next,val);
//判断头节点情况
//if(head.val == val){
// return head.next;
//}
// return head;
return head.next == val ? head.next:head;
}