Skip to content

Latest commit

 

History

History
120 lines (100 loc) · 2.5 KB

203.remove-linked-list-elements.md

File metadata and controls

120 lines (100 loc) · 2.5 KB

题目地址

https://leetcode.com/problems/remove-linked-list-elements/description/

题目描述

Remove all elements from a linked list of integers that have value val.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

思路

这个一个链表基本操作的题目,思路就不多说了。

关键点解析

  • 链表的基本操作(删除指定节点)
  • 虚拟节点dummy 简化操作

其实设置dummy节点就是为了处理特殊位置(头节点),这这道题就是如果头节点是给定的需要删除的节点呢? 为了保证代码逻辑的一致性,即不需要为头节点特殊定制逻辑,才采用的虚拟节点。

  • 如果连续两个节点都是要删除的节点,这个情况容易被忽略。 eg:
// 只有下个节点不是要删除的节点才更新current
if (!next || next.val !== val) {
    current =  next;
}

代码

  • 语言支持:JS,Python

Javascript Code:

/*
 * @lc app=leetcode id=203 lang=javascript
 *
 * [203] Remove Linked List Elements
 *
 * https://leetcode.com/problems/remove-linked-list-elements/description/
 *
 * algorithms
 * Easy (35.32%)
 * Total Accepted:    211.9K
 * Total Submissions: 598.6K
 * Testcase Example:  '[1,2,6,3,4,5,6]\n6'
 *
 * Remove all elements from a linked list of integers that have value val.
 *
 * Example:
 *
 *
 * Input:  1->2->6->3->4->5->6, val = 6
 * Output: 1->2->3->4->5
 *
 *
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const dummy = {
        next: head
    }
    let current = dummy;

    while(current && current.next) {
        let next = current.next;
        if (next.val === val) {
            current.next = next.next;
            next = next.next;
        }

        if (!next || next.val !== val) {
            current =  next;
        }
    }

    return dummy.next;
};

Python Code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        prev = ListNode(0)
        prev.next = head
        cur = prev
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return prev.next