代码随想录03:链表

BBigSun 评论178阅读模式

代码随想录03:链表

理论基础

  • 单链表:一个数据域 + 一个指针域(指向下个节点),最后一个节点指向空。
  • 双链表:一个数据域 + 两个指针域(一个指向上个节点,一个指向下个节点)。
  • 循环链表:链表首位相连。

链表定义

struct ListNode {
    int val;    // 节点上存储的值
    ListNode *next; // 指向下个节点的指针
    ListNode(int x): val(x), next(NULL) {}  // 节点构造函数
};
class ListNode:
    def __init__(self, val, next=None):
    self.val = val
    self.next = next

删除节点

当前指针指向下下个节点,回收删除的节点内存文章源自十年又十年-https://www.bbigsun.com/406.html

添加节点

当前指针指向添加的节点,添加的节点的指针指向下个节点。文章源自十年又十年-https://www.bbigsun.com/406.html

移除链表元素

问题:删除链表中等于给定值 val 的所有节点文章源自十年又十年-https://www.bbigsun.com/406.html

示例 1:输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]文章源自十年又十年-https://www.bbigsun.com/406.html

示例 2: 输入:head = [], val =1, 输出:[]文章源自十年又十年-https://www.bbigsun.com/406.html

示例 3:输入:head = [7,7,7,7], val = 7 输出:[]文章源自十年又十年-https://www.bbigsun.com/406.html

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

设计链表

题意:文章源自十年又十年-https://www.bbigsun.com/406.html

在链表中实现以下功能:文章源自十年又十年-https://www.bbigsun.com/406.html

  • get(index)
文章源自十年又十年-https://www.bbigsun.com/406.html文章源自十年又十年-https://www.bbigsun.com/406.html

纸上得来终觉浅,绝知此事要躬行。

weinxin
17688689121
我的微信
微信扫一扫
BBigSun
  • 本文由 BBigSun 发表于 2023年 3月 30日 16:40:04
  • 转载请务必保留本文链接:https://www.bbigsun.com/406.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定