Java移除链表元素

目录

1.题目描述

2.题解

题解1

题解2

---

1.题目描述

给你一个链表的头节点 head 和一个整数 val，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例

输入：head = [1,2,6,3,4,5,6]，val = 6

输出：[1,2,3,4,5]

输入：head = [], val = 1
输出：[]

输入：head = [7,7,7,7], val = 7
输出：[]

2.题解

题解1

思路分析：创建新的链表，将链表中值不为val的节点尾插到新的节点中。

利用cur遍历原来链表，tail遍历新的链表，若cur的值不为val，则将cur赋值给tail，cur向后移动，若cur的值为val，则跳过该节点。

//创建新链表ListNode newHead = null;ListNode cur = head;ListNode tail = null;    while(cur != null){    if(cur.val != val) {        //第一次插入        if (tail == null) {            newHead = tail = cur;        } else {            tail.next = cur;            tail = cur;        }    }    cur = cur.next;}

由于tail的值可能不为空，此时我们需要将新链表的尾部置空

//尾部置空if(tail != null){    tail.next = null;}

完整代码

class Solution {    public ListNode removeElements(ListNode head, int val) {        //若链表为空，则直接返回null        if(head == null){            return null;        }        //创建新链表        ListNode newHead = null;        ListNode cur = head;        ListNode tail = null;        while(cur != null){            if(cur.val != val) {                //第一次插入                if (tail == null) {                    newHead = tail = cur;                } else {                    tail.next = cur;                    tail = cur;                }            }            cur = cur.next;        }        //尾部置空        if(tail != null){            tail.next = null;        }        return newHead;    }}

题解2

思路分析：要想删除链表中的元素，首先要找到值为val的节点node，将node的上一节点指向node的下一节点，即可删除值为val的节点，注意考虑头节点为val的情况，要删除链表中所有值为val的节点，利用while循环即可实现。

由于链表为单链表，因此需要保存值为val节点node的上一个节点，可以创建prev和cur，cur指向当前节点，prev指向当前节点的上一节点，也可以通过cur.next.val找到值为val的节点

ListNode cur = head;while(cur.next != null){    if(cur.next.val == val){        cur.next = cur.next.next;    }else{        cur = cur.next;    }}

当头节点的值也为val时，则需单独删除头节点

if(head.val == val){    head = head.next;}

完整代码

class Solution {    public ListNode removeElements(ListNode head, int val) {        //若链表为空，则直接返回null        if(head == null){            return null;        }        ListNode cur = head;        while(cur.next != null){            if(cur.next.val == val){                cur.next = cur.next.next;            }else{                cur = cur.next;            }        }        //单独考虑头节点的值是否等于val        if(head.val == val){            head = head.next;        }        return head;    }}

题目来源：

203. 移除链表元素 - 力扣（LeetCode）

来源地址：https://blog.csdn.net/2301_76161469/article/details/133071093