Java教程

链表算法题(1)移除链表元素

本文主要是介绍链表算法题(1)移除链表元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

移除链表元素

描述

示例 1

示例 2

示例 3

提示

数据结构

方法:双指针


移除链表元素

描述

给你一个链表的头节点 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
输出:[]

提示

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

数据结构

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

方法:双指针

本题用cur指针指向当前节点,pre指针指向当前节点的前面一个节点,即pre.next=cur

我们在遍历的时候当cur.val==val时,就让前面节点的next指向cur的next,即pre.next=cur.next。

需要注意的是,如果要删除头节点,我们需要引入一个虚拟头节点node,让node.next=head,这样开始pre=node、cur=head,此时就可以按照前面的删除操作删除头节点了。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur=head;
        ListNode res=new ListNode(0);
        res.next=head;
        ListNode pre=res;
        while (cur!=null){
            if (cur.val==val){//如果当前值为要删除的元素
                pre.next=cur.next;//删除中间节点
                cur=cur.next;//此时pre不变,cur后移
            }else{
                pre=cur;//此时pre也后移
                cur=cur.next;//cur后移
            }
        }
        return res.next;
    }
}

这篇关于链表算法题(1)移除链表元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!