C++实现LeetCode(203.移除链表元素)

[LeetCode] 203.Remove Linked List Elements 移除链表元素

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

Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

这道移除链表元素是链表的基本操作之一，没有太大的难度，就是考察了基本的链表遍历和设置指针的知识点，我们只需定义几个辅助指针，然后遍历原链表，遇到与给定值相同的元素，将该元素的前后连个节点连接起来，然后删除该元素即可，要注意的是还是需要在链表开头加上一个dummy node，具体实现参见代码如下：

解法一：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        while (pre->next) {
            if (pre->next->val == val) {
                ListNode *t = pre->next;
                pre->next = t->next;
                t->next = NULL;
                delete t;
            } else {
                pre = pre->next;
            }
        }
        return dummy->next;
    }
};

如果只是为了通过OJ，不用写的那么严格的话，下面这种方法更加简洁，当判断下一个结点的值跟给定值相同的话，直接跳过下一个结点，将next指向下下一个结点，而根本不断开下一个结点的next，更不用删除下一个结点了。最后还要验证头结点是否需要删除，要的话直接返回下一个结点，参见代码如下：

解法二：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return NULL;
        ListNode *cur = head;
        while (cur->next) {
            if (cur->next->val == val) cur->next = cur->next->next;
            else cur = cur->next;
        }
        return head->val == val ? head->next : head;
    }
};

我们也可以用递归来解，写法很简洁，通过递归调用到链表末尾，然后回来，需要要删的元素，将链表next指针指向下一个元素即可：

解法三：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head) return NULL;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

类似题目：

Remove Element

Delete Node in a Linked List

参考资料：

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

https://leetcode.com/problems/remove-linked-list-elements/discuss/57324/AC-Java-solution

https://leetcode.com/problems/remove-linked-list-elements/discuss/57306/3-line-recursive-solution

https://leetcode.com/problems/remove-linked-list-elements/discuss/57331/Accepted-7-line-clean-java-solution

到此这篇关于C++实现LeetCode(203.移除链表元素)的文章就介绍到这了,更多相关C++实现移除链表元素内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(199.二叉树的右侧视图)

    [LeetCode] 199.Binary Tree Right Side View 二叉树的右侧视图 Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1     

  • C++实现LeetCode(309.买股票的最佳时间含冷冻期)

    [LeetCode] 309.Best Time to Buy and Sell Stock with Cooldown 买股票的最佳时间含冷冻期 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as

  • C++实现LeetCode(198.打家劫舍)

    [LeetCode] 198. House Robber 打家劫舍 You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security

  • C++实现LeetCode(201.数字范围位相与)

    [LeetCode] 201.Bitwise AND of Numbers Range 数字范围位相与 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive. For example, given the range [5, 7], you should return 4. Credits: Special t

  • C++实现LeetCode(188.买卖股票的最佳时间之四)

    [LeetCode] 188.Best Time to Buy and Sell Stock IV 买卖股票的最佳时间之四 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most k transactions. Note: You m

  • C++实现LeetCode(190.颠倒二进制位)

    [LeetCode] 190. Reverse Bits 颠倒二进制位 Reverse bits of a given 32 bits unsigned integer. Example 1: Input: 00000010100101000001111010011100 Output: 00111001011110000010100101000000 Explanation: The input binary string 00000010100101000001111010011100 re

  • C++实现LeetCode(237.删除链表的节点)

    [LeetCode] 237.Delete Node in a Linked List 删除链表的节点 Write a function to delete a node (except the tail) in a singly linked list, given only access to that node. Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with va

  • C++实现LeetCode(202.快乐数)

    [LeetCode] 202.Happy Number 快乐数 Write an algorithm to determine if a number is "happy". A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits,

  • C++实现LeetCode(203.移除链表元素)

    [LeetCode] 203.Remove Linked List Elements 移除链表元素 Remove all elements from a linked list of integers that have value val. Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5 Credits

  • C++实现LeetCode(19.移除链表倒数第N个节点)

    C++实现LeetCode(19.移除链表倒数第N个节点)

    [LeetCode] 19. Remove Nth Node From End of List 移除链表倒数第N个节点 Given a linked list, remove the nth node from the end of list and return its head. For example, Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the en

  • C++逆向分析移除链表元素实现方法详解

    目录 前言 题目描述 debug版汇编代码 分析 源代码 前言 这次的题目可以练习到循环加结构体数组和ifelse的大量嵌套. 逆向这种东西就是一个经验的积累,做得多了就会有感觉,这次的分析我会详细写一下如何判断哪里是if哪里是while这种逻辑判断. 题目描述 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 . debug版汇编代码 004E3580  push        ebp  004E3581

  • C++实现LeetCode(82.移除有序链表中的重复项之二)

    [LeetCode] 82. Remove Duplicates from Sorted List II 移除有序链表中的重复项之二 Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Example 1: Input: 1->2->3->3->4->4->5 Outp

  • C++实现LeetCode(83.移除有序链表中的重复项)

    [LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-

  • C++实现LeetCode(27.移除元素)

    [LeetCode] 27. Remove Element 移除元素 Given an array nums and a value val, remove all instances of that value in-place and return the new length. Do not allocate extra space for another array, you must do this by modifying the input array in-place with

  • C++实现LeetCode(109.将有序链表转为二叉搜索树)

    [LeetCode] 109.Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树 Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary

  • java中LinkedList使用迭代器优化移除批量元素原理

    java中LinkedList使用迭代器优化移除批量元素原理

    本文主要介绍了java中LinkedList使用迭代器优化移除批量元素原理,分享给大家,具体如下: public interface Iterator<E> { /** *是否还有下一个元素 */ boolean hasNext(); /** *下一个元素 */ E next(); /** * 从集合中删除最后一个返回的元素 */ default void remove() { throw new UnsupportedOperationException("remove"

  • 利用PHP实现递归删除链表元素的方法示例

    前言 这篇文章介绍一下 递归,递归的本质是将原来的问题转化为更小的同一个问题,解决这些更小问题的过程.下面通过两个递归的例子帮助学习对递归的理解. 1.递归数组求和 例如某个数组 $arr = [1,2,3,4,5,6,7,8,9,10]; 需要求和,通过实现递归函数对数组求和来帮助学习对递归的理解. 1.1 输出文件 output_recursion.php <?php require 'ArrayRecursion.php'; /** * 递归实现数组求和 */ $arr = [1, 2,

  • Java List移除相应元素的超简洁写法分享

    Java List移除相应元素的超简洁写法分享

    目录 List移除相应元素的超简洁写法 好了上代码 Java List 删除元素 1.删除后元素后,i-1 2.反向删除 3.使用迭代器删除(iterator)(推荐) 4.赋值给新的list List移除相应元素的超简洁写法 最近遇到了一个需求(好吧以前也遇到过),就是将一个List中的部分元素去除,如把string中带数字的元素去除,以前是各种遍历各种不爽,今天发现用Java8中的lambda写,只需三行. 好了上代码 List<String> list = new ArrayList&l

随机推荐