1. Toy模板网首页
  2. > Toy博客

算法刷题-链表-移除链表元素

7月前 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了算法刷题-链表-移除链表元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点再进行删除操作，接下来看一看哪种方式更方便。

203.移除链表元素

力扣题目链接

题意：删除链表中等于给定值 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
输出：[]

思路

这里以链表 1 4 2 4 来举例，移除元素4。

算法刷题-链表-移除链表元素

如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点， 清理节点内存之后如图：

算法刷题-链表-移除链表元素

当然如果使用java ，python的话就不用手动管理内存了。

还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养成手动清理内存的习惯。

这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里就涉及如下链表操作的两种方式：

  • 直接使用原来的链表来进行删除操作。
  • 设置一个虚拟头结点在进行删除操作。

来看第一种操作：直接使用原来的链表来进行移除。

算法刷题-链表-移除链表元素

移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

算法刷题-链表-移除链表元素

依然别忘将原头结点从内存中删掉。
算法刷题-链表-移除链表元素

这样移除了一个头结点，是不是发现，在单链表中移除头结点 和 移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

那么可不可以 以一种统一的逻辑来移除 链表的节点呢。

其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

算法刷题-链表-移除链表元素

这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

这样是不是就可以使用和移除链表其他节点的方式统一了呢？

来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;， 这才是新的头结点

C++代码

直接使用原来的链表来进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 删除头结点
        while (head != NULL && head->val == val) { // 注意这里不是if
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

        // 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        return head;
    }
};

设置一个虚拟头结点在进行移除节点操作：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            } else {
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

其他语言版本

C:
用原来的链表操作：

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* temp;
    // 当头结点存在并且头结点的值等于val时
    while(head && head->val == val) {
        temp = head;
        // 将新的头结点设置为head->next并删除原来的头结点
        head = head->next;
        free(temp);
    }

    struct ListNode *cur = head;
    // 当cur存在并且cur->next存在时
    // 此解法需要判断cur存在因为cur指向head。若head本身为NULL或者原链表中元素都为val的话，cur也会为NULL
    while(cur && (temp = cur->next)) {
        // 若cur->next的值等于val
        if(temp->val == val) {
            // 将cur->next设置为cur->next->next并删除cur->next
            cur->next = temp->next;
            free(temp);
        }
        // 若cur->next不等于val，则将cur后移一位
        else
            cur = cur->next;
    }

    // 返回头结点
    return head;
}

设置一个虚拟头结点：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* removeElements(struct ListNode* head, int val){
    typedef struct ListNode ListNode;
    ListNode *shead;
    shead = (ListNode *)malloc(sizeof(ListNode));
    shead->next = head;
    ListNode *cur = shead;
    while(cur->next != NULL){
        if (cur->next->val == val){
            ListNode *tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
        }
        else{
            cur = cur->next;
        }
    }
    head = shead->next;
    free(shead);
    return head;
}

Java：

/**
 * 添加虚节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}
/**
 * 不添加虚拟节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while (head != null && head.val == val) {
        head = head.next;
    }
    // 已经为null，提前退出
    if (head == null) {
        return head;
    }
    // 已确定当前head.val != val
    ListNode pre = head;
    ListNode cur = head.next;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}
/**
 * 不添加虚拟节点and pre Node方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 * @param head
 * @param val
 * @return
 */
public ListNode removeElements(ListNode head, int val) {
    while(head!=null && head.val==val){
        head = head.next;
    }
    ListNode curr = head;
    while(curr!=null){
        while(curr.next!=null && curr.next.val == val){
            curr.next = curr.next.next;
        }
        curr = curr.next;
    }
    return head;
}

Python：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(next=head) #添加一个虚拟节点
        cur = dummy_head
        while(cur.next!=None):
            if(cur.next.val == val):
                cur.next = cur.next.next #删除cur.next节点
            else:
                cur = cur.next
        return dummy_head.next

Go：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head
    cur := dummyHead
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return dummyHead.Next
}

javaScript:

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    const ret = new ListNode(0, head);
    let cur = ret;
    while(cur.next) {
        if(cur.next.val === val) {
            cur.next =  cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return ret.next;
};

TypeScript:

版本一（在原链表上直接删除）：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function removeElements(head: ListNode | null, val: number): ListNode | null {
    // 删除头部节点
    while (head !== null && head.val === val) {
        head = head.next;
    }
    if (head === null) return head;
    let pre: ListNode = head, cur: ListNode | null = head.next;
    // 删除非头部节点
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next;
        } else {
            //此处不加类型断言时：编译器会认为pre类型为ListNode, pre.next类型为ListNode | null
            pre = pre.next as ListNode;
        }
        cur = cur.next;
    }
    return head;
};

版本二（虚拟头节点）：

function removeElements(head: ListNode | null, val: number): ListNode | null {
    // 添加虚拟节点
    const data = new ListNode(0, head);
    let pre = data, cur = data.next;
    while (cur) {
        if (cur.val === val) {
            pre.next = cur.next
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return data.next;
};

Swift：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
func removeElements(_ head: ListNode?, _ val: Int) -> ListNode? {
    let dummyNode = ListNode()
    dummyNode.next = head
    var currentNode = dummyNode
    while let curNext = currentNode.next {
        if curNext.val == val {
            currentNode.next = curNext.next
        } else {
            currentNode = curNext
        }
    }
    return dummyNode.next
}

PHP:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 虚拟头+双指针
func removeElements(head *ListNode, val int) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head
    pred := dummyHead
    cur := head
    for cur != nil {
        if cur.Val == val {
            pred.Next = cur.Next
        } else {
            pred = cur
        }
        cur = cur.Next
    }
    return dummyHead.Next
}

RUST:

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn remove_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
        let mut dummyHead = Box::new(ListNode::new(0));
        dummyHead.next = head;
        let mut cur = dummyHead.as_mut();
	// 使用take()替换std::men::replace(&mut node.next, None)达到相同的效果，并且更普遍易读
        while let Some(nxt) = cur.next.take() {
            if nxt.val == val {
                cur.next = nxt.next;
            } else {
                cur.next = Some(nxt);
                cur = cur.next.as_mut().unwrap();
            }
        }
        dummyHead.next
    }
}

Scala:

/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
  def removeElements(head: ListNode, `val`: Int): ListNode = {
    if (head == null) return head
    var dummy = new ListNode(-1, head) // 定义虚拟头节点
    var cur = head // cur 表示当前节点
    var pre = dummy // pre 表示cur前一个节点
    while (cur != null) {
      if (cur.x == `val`) {
        // 相等，就删除那么cur的前一个节点pre执行cur的下一个
        pre.next = cur.next
      } else {
        // 不相等，pre就等于当前cur节点
        pre = cur
      }
      // 向下迭代
      cur = cur.next
    }
    // 最终返回dummy的下一个，就是链表的头
    dummy.next
  }
}

Kotlin:文章来源地址https://www.toymoban.com/news/detail-479344.html

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun removeElements(head: ListNode?, `val`: Int): ListNode? {
        // 使用虚拟节点，令该节点指向head
        var dummyNode = ListNode(-1)
        dummyNode.next = head
        // 使用cur遍历链表各个节点
        var cur = dummyNode
        // 判断下个节点是否为空
        while (cur.next != null) {
            // 符合条件，移除节点
            if (cur.next.`val` == `val`) {
                cur.next = cur.next.next
            }
            // 不符合条件，遍历下一节点
            else {
                cur = cur.next
            }
        }
        // 注意：返回的不是虚拟节点
        return dummyNode.next
    }
}

到了这里，关于算法刷题-链表-移除链表元素的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【代码随想录刷题记录】 203.移除链表元素 、 707.设计链表 、206.反转链表

    题目 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 题目链接:https://leetcode.cn/problems/remove-linked-list-elements/ 代码 小结 该题主要注意链表删除的操作以及在特殊情况下如何进行操作。特殊情况包括头结点为目标

    2024年02月08日
    浏览(33)
  • 算法-设计链表、移除链表元素、反转链表

    算法-设计链表、移除链表元素、反转链表

    伪装成一个老手！ 设计一个单链表，其中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。 实现 MyLinkedList 类： MyLinkedList()初始化 MyLinkedList 对象。 int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1

    2024年02月11日
    浏览(81)
  • 刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

    刷题日记 Day 3 : Leetcode 203 . 移除链表元素、Leetcode 707 . 设计链表、Lettcode 206 . 反转链表

    本篇文章 , 是在代码随想录 60 天编程挑战的基础上进行的题目讲解 参与链接在此 : https://programmercarl.com/other/xunlianying.html 大家好 , 这个专栏 , 给大家带来的是 60 天刷题强训 . 最令大家头疼的事就是刷题了 , 题目又臭又长又抽象 , 有的题读都读不懂 , 更别说做了 . 所以 , 这个

    2023年04月09日
    浏览(37)
  • 单链表相关经典算法OJ题：移除链表元素

    单链表相关经典算法OJ题：移除链表元素

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 目录 前言 题目：移除链表元素 解法一： 解法一的代码实现： 解法二： 解法二代码的实现： 总结 世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各

    2024年02月04日
    浏览(37)

  • 算法训练第三天|203.移除链表元素、707.设计链表、206.反转链表

    题目链接：力扣 思路：删除链表元素与数组不同之处在于，它需要被删除链表元素的前一个元素和后一个元素的参与，而不需要其他元素的参与。 我们使被删除元素前一个元素的指针指向被删除元素的后一个元素 ，也就是直接跳过被删除的元素，来实现删除。 同时我们考

    2024年02月05日
    浏览(27)
  • 算法题：203. 移除链表元素（递归法、设置虚拟头节点法等3种方法）Java实现创建链表与解析链表

    算法题：203. 移除链表元素（递归法、设置虚拟头节点法等3种方法）Java实现创建链表与解析链表

    讲一下设置虚拟头节点的那个方法，设置一个新节点指向原来链表的头节点，这样我们就可以通过判断链表的当前节点的后继节点值是不是目标删除值，来判断是否删除这个后继节点了。如果不设置虚拟头节点，则需要将头节点和后面的节点分开来讨论，代码会复杂一点。

    2024年02月05日
    浏览(31)
  • 移除链表元素

    移除链表元素

    ☃️个人主页：fighting小泽 🌸作者简介：目前正在学习C语言和数据结构 🌼博客专栏：leetcode练习题 🏵️欢迎关注：评论👊🏻点赞👍🏻留言💪🏻 题目链接： 移除链表元素 给你一个链表的头节点 head 和一个整数 val ，请你 删除链表中所有满足 Node.val == val 的节点 ， 并返

    2024年02月04日
    浏览(30)
  • 203.移除链表元素

    203.移除链表元素

    循环遍历整个链表 定义两个指针：prev，cur 如果cur是要删除的节点，prev-cur-next，然后free(cur) 但是注意每次都要新定义一个节点del，用来free，不影响原来的cur节点往下循环 更新cur和prev 但是需要注意如果删除的是头节点，就要特殊处理，画图带上指针，情况分析，一目了然。

    2024年01月22日
    浏览(34)
  • 移除链表元素详解

    移除链表元素详解

      原题出处： . - 力扣（LeetCode） 我们可以新创建一个链表，然后将不等于val的节点拿下来进行尾插，这样的方式更加简易，只需要遍历整个链表即可。 我们首先使用一个指针cur来遍历原链表，来获取不等于val的节点。 如果cur的next等于val就跳过这个节点，如果不等于val就尾

    2024年04月26日
    浏览(30)
  • Java移除链表元素

    Java移除链表元素

    目录 1.题目描述 2.题解 题解1 题解2 给你一个链表的头节点 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 输出：

    2024年02月07日
    浏览(24)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包