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）