203. 移除链表元素

本题来自 LeetCode：203. 移除链表元素^[1]

题目描述

删除链表中等于给定值 val 的所有节点。
示例:

输入: 1-2-6-3-4-5-6, val = 6
输出: 1-2-3-4-5

题目分析

采用单指针遍历链表，判断下一个节点是否为给定值，若是，则直接删掉；否则继续遍历。
需要注意的是，要特殊考虑首节点为给定值的情况。

题目解答

解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 考虑首节点值为val的情况
        while(head != null && head.val == val) {
            head = head.next;
        }
        ListNode cur = head;
        while(cur != null) {
                // 若next节点等于val，直接删掉next节点
            if(cur.next != null && cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                // next节点为null，或next节点不等于val
                cur = cur.next;
            }
        }
        return head;
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(1)

解法二

添加辅助节点后，就不需要考虑首节点为给定值的情况。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        while(cur.next != null) {
            if(cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

复杂度分析：
时间复杂度： O(n)
空间复杂度： O(1)

参考资料

203. 移除链表元素: https://leetcode-cn.com/problems/remove-linked-list-elements/

原文始发于微信公众号（xiaogan的技术博客）：