【LeetCode】203.移除链表元素

203.移除链表元素

知识点：链表

题目描述

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

解法一

思路是很简单的，就是遍历链表，当遇到与val值相等的时候就将其前面节点直接指向后面节点，也就是直接忽略（隔掉）当前节点，所以可知得用两个指针一个保持当前节点，一个保持当前节点的上一个节点；并且最后返回的是ListNode，所以需要用一个虚拟头指针，里面的数据无所谓，主要是为了操作方便，使链表永不为空，永不无头等功能。

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyNode = new ListNode(0);  //定义虚拟头节点；
        dummyNode.next = head;  //虚头指向实头；
        ListNode cur = head;   //定义一个指针，指向当前节点；
        ListNode pre = dummyNode;  //定义一个指针，指向前一节点；
        while(cur != null){
            if(cur.val == val) pre.next = cur.next;
            else pre = cur;
            cur = cur.next;  
        }
        return dummyNode.next;
    }
}

时间复杂度：O(N);

体会

这里链表的第一道题，从中也可以看出一些对链表常用的一些操作：虚拟头节点；前一节点；当前节点；这都是需要在链表的问题中关注的。
除此之外，还有明白这个代码中的关系，虽然在java中没有指针，但是要知道比如其中定义当前指针这句话在内存中是怎么存在的，知道为什么最后返回dummyNode.next；cur和pre都只是获得了一个地址值，都是对应的在内存中实际存在的一个链表进行的操作。

【LeetCode】203.移除链表元素

原文：https://www.cnblogs.com/Curryxin/p/14776378.html