首页 > 编程语言 >代码随想录算法训练营第三天|203移除链表元素 707设计链表 206反转链表

代码随想录算法训练营第三天|203移除链表元素 707设计链表 206反转链表

时间：2024-09-17 19:23:41浏览次数：3  
标签：index cur val self current 随想录 next 链表 移除

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 输出：[]

链表一直是处理的不太好的数据结构，太久没处理过，第一次做链表题容易直接定义一个临时的cur节点变量等于需要判断的节点，由于是在单向链表的场景下，如果判断出该节点需要被删除，那么我们无法对上一个节点进行操作（需要让【该删除的节点】的上一个节点指向【该删除的节点】的下一个节点），这样就无法继续了。

所以思路就是上述括号这样，但是代码的完成和完整性需要考虑的仔细一点，在代码实现的时候，应该让临时节点cur的next指向被判断的节点，也就是cur应该作为【被判断节点】的前一个节点，判断删除的时候，直接让cur节点next绕过被删除节点即可。（python自动释放，C++手动释放被删除节点）

以下为代码的实现：

# 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: Optional[ListNode], val: int) -> Optional[ListNode]:

        while head and head.val == val:

            head = head.next #当头部节点为被删除节点，头部改为下一个节点，直到不是被删除节点（可能全是，最后剩下空链表）



        cur = ListNode(next = head)



        while cur.next:

            if cur.next.val == val:

                cur.next = cur.next.next

            else:

                cur = cur.next



        return head

代码随想录提供【虚拟头结点】的方法：

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

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

理解下来发现和我自己的实现也是大同小异的思路，但是更加规范化了，也更公式化，有利于后续类似题目提高做题速度，记录一下：

虚拟头节点法

# 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: Optional[ListNode], val: int) -> Optional[ListNode]:

        # 创建虚拟头部节点以简化删除过程

        dummy_head = ListNode(next = head)

        

        # 遍历列表并删除值为val的节点

        current = dummy_head

        while current.next:

            if current.next.val == val:

                current.next = current.next.next

            else:

                current = current.next

        

        return dummy_head.next

707.设计链表

题意：

在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

707示例

思路还是使用推荐的虚头部节点，在ListNode结构中设置val和next，在List中设置虚头部dummyhead和size（为了判断索引是否正确）。

Debug问题主要出在：

  1. 声明cur节点的方式不太好，使用了构造函数，反而导致出现很多问题，还是掌握的不太好，直接令其等于dummyhead其实就可以了。至于事等于dummyhead还是dummyhead.next，根据函数的作用和目标来理解即可。
  2. 对数据结构和对象的构造函数、属性、self的使用等不熟练，这一题强化了自己的掌握度。
  3. 虽然最后debug出来了，但还是有很多习惯不太好，应借鉴规范代码改进。
  4. Debug中的一个问题补充一段AI的说明改正：ListNode=None 出现在 MyLinkedList 类的构造函数中，这是一个错误的用法。ListNode 应该是一个类，而不是一个值。您可能想要将 None 赋给 dummyhead.next，表示链表开始时为空。

在 MyLinkedList 类中，dummyhead 是一个哑节点（也称为哨兵节点），它不是链表的一部分，但是作为链表的头部，使得我们可以统一处理头部和中间节点的添加和删除操作。哑节点不存储任何实际的数据，它的 next 指针指向链表的第一个实际节点。

以下为代码实现：

class ListNode:
   def __init__(self, val=0, next=None):
       self.val = val
       self.next = next


class MyLinkedList:
   def __init__(self):
   #def __init__(self, ListNode=None)   # 自己瞎补充的None导致debug了很久。。也没想起来为啥自己这么写
       # self.head = ListNode          # 根据代码随想录的指引，还是使用虚头部，使用了虚头部后head多余了
       self.dummyhead = ListNode()    # 初始化0
       self.size = 0

   def get(self, index: int) -> int:
       if index<0 or index>=self.size:
           return -1
       # cur = ListNode(next=self.dummyhead.next)  # 直接使用 self.dummyhead 而不是创建一个新的 ListNode 实例。
       cur = self.dummyhead.next
       for i in range(index):
           cur = cur.next
       #return cur.next.val
       return cur.val

   def addAtHead(self, val: int) -> None:
       newHead = ListNode(val=val)
       newHead.next = self.dummyhead.next
       self.dummyhead.next = newHead
       self.size += 1

   def addAtTail(self, val: int) -> None:
       #cur = ListNode(next=self.dummyhead.next)   #直接使用 self.dummyhead 而不是创建一个新的 ListNode 实例。
       cur = self.dummyhead.next
       #for i in range(self.size):             # 找尾部直接用while不用for
       #    cur = cur.next
       while cur.next:
           cur = cur.next
       newTail = ListNode(val=val)
       #cur.next.next = newTail
       cur.next = newTail
       self.size += 1

   def addAtIndex(self, index: int, val: int) -> None:
       if index > self.size:
           return
       #cur = ListNode(next=self.dummyhead.next)   #直接使用 self.dummyhead 而不是创建一个新的 ListNode 实例。
       cur = self.dummyhead
       for i in range(index):
           cur = cur.next
       newNode = ListNode(val, cur.next)
       cur.next = newNode
       self.size += 1

   def deleteAtIndex(self, index: int) -> None:
       if index<self.size:
           #cur = ListNode(next=self.dummyhead.next) #直接使用 self.dummyhead 而不是创建一个新的 ListNode 实例。
           cur = self.dummyhead
           for i in range(index):
               cur = cur.next
           cur.next = cur.next.next
           self.size -= 1

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

规范代码：

class ListNode:

    def __init__(self, val=0, next=None):

        self.val = val

        self.next = next

        class MyLinkedList:

    def __init__(self):

        self.dummy_head = ListNode()

        self.size = 0



    def get(self, index: int) -> int:

        if index < 0 or index >= self.size:

            return -1

        

        current = self.dummy_head.next

        for i in range(index):

            current = current.next

            

        return current.val



    def addAtHead(self, val: int) -> None:

        self.dummy_head.next = ListNode(val, self.dummy_head.next)

        self.size += 1



    def addAtTail(self, val: int) -> None:

        current = self.dummy_head

        while current.next:

            current = current.next

        current.next = ListNode(val)

        self.size += 1



    def addAtIndex(self, index: int, val: int) -> None:

        if index < 0 or index > self.size:

            return

        

        current = self.dummy_head

        for i in range(index):

            current = current.next

        current.next = ListNode(val, current.next)

        self.size += 1



    def deleteAtIndex(self, index: int) -> None:

        if index < 0 or index >= self.size:

            return

        

        current = self.dummy_head

        for i in range(index):

            current = current.next

        current.next = current.next.next

        self.size -= 1



# Your MyLinkedList object will be instantiated and called as such:# obj = MyLinkedList()# param_1 = obj.get(index)# obj.addAtHead(val)# obj.addAtTail(val)# obj.addAtIndex(index,val)# obj.deleteAtIndex(index)

基本没有大问题，和规范代码思路基本一致。

这次没时间写多一个双向链表的实现了，先将规范代码记录，理解之后后面抽一天回来闭卷补了。

（版本二）双链表法

class ListNode:

    def __init__(self, val=0, prev=None, next=None):

        self.val = val

        self.prev = prev

        self.next = next

class MyLinkedList:

    def __init__(self):

        self.head = None

        self.tail = None

        self.size = 0



    def get(self, index: int) -> int:

        if index < 0 or index >= self.size:

            return -1

        

        if index < self.size // 2: # 整数除法，确保得出的数是整数

            current = self.head

            for i in range(index):

                current = current.next

        else:

            current = self.tail

            for i in range(self.size - index - 1):

                current = current.prev

                

        return current.val



    def addAtHead(self, val: int) -> None:

        new_node = ListNode(val, None, self.head)

        if self.head:

            self.head.prev = new_node

        else:

            self.tail = new_node

        self.head = new_node

        self.size += 1



    def addAtTail(self, val: int) -> None:

        new_node = ListNode(val, self.tail, None)

        if self.tail:

            self.tail.next = new_node

        else:

            self.head = new_node

        self.tail = new_node

        self.size += 1



    def addAtIndex(self, index: int, val: int) -> None:

        if index < 0 or index > self.size:

            return

        

        if index == 0:

            self.addAtHead(val)

        elif index == self.size:

            self.addAtTail(val)

        else:

            if index < self.size // 2:

                current = self.head

                for i in range(index - 1):

                    current = current.next

            else:

                current = self.tail

                for i in range(self.size - index):

                    current = current.prev

            new_node = ListNode(val, current, current.next)

            current.next.prev = new_node

            current.next = new_node

            self.size += 1



    def deleteAtIndex(self, index: int) -> None:

        if index < 0 or index >= self.size:

            return

        

        if index == 0:

            self.head = self.head.next

            if self.head:

                self.head.prev = None

            else:

                self.tail = None

        elif index == self.size - 1:

            self.tail = self.tail.prev

            if self.tail:

                self.tail.next = None

            else:

                self.head = None

        else:

            if index < self.size // 2:

                current = self.head

                for i in range(index):

                    current = current.next

            else:

                current = self.tail

                for i in range(self.size - index - 1):

                    current = current.prev

            current.prev.next = current.next

            current.next.prev = current.prev

        self.size -= 1





# Your MyLinkedList object will be instantiated and called as such:# obj = MyLinkedList()# param_1 = obj.get(index)# obj.addAtHead(val)# obj.addAtTail(val)# obj.addAtIndex(index,val)# obj.deleteAtIndex(index)

206.反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

由于正常的思路过于好想，新建一个链表的思路肯定不是所考察的内容，所以第一时间也懒得去实现了。直接看到了今天的提示：双指针和递归。

试着自己实现双指针的思路：

一个prev指针，一个cur指针，思路肯定是让cur指向prev，然后再往后平移，依次让节点指向往前指，但是由于只看了双指针法的字面意思，一直认定只需要两个指针就能实现，所以虽然自己想到了用tem存储【原】cur.next的位置，但还是限制自己去用这个方法存放，后面发现好像无论如何会使得链表中断，忍不住看了解析，发现确实还是用了temp，看来这个用来存放的节点变量不能当作指针，有点苦笑不得。那么实现就简单了，明白思路后两分钟就速通了代码：

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        prev = None

        cur = head

        while cur:

            tem = cur.next

            cur.next = prev

            prev = cur

            cur = tem

        return prev

看了视频，卡哥讲的太清晰易懂了，把递归也实现一下。

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, val=0, next=None):

#         self.val = val

#         self.next = next

class Solution:

    def reverse(self, prev:ListNode, cur:ListNode) -> ListNode: #在类中新定义一个def，定义这行括号里需要self，用于构造函数，由于返回的是一个ListNode，括号后需要->ListNode

        if not cur:

            return prev # 递归返回条件是cur为空

        tem = cur.next

        cur.next = prev

        return self.reverse(cur, tem) # 调用递归函数需要self.reverse（） 括号里不需要带self

   

   

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        prev = None

        cur = head

        return self. reverse(prev, cur) # 调用类中其他def需要用self

       

标签：index,cur,val,self,current,随想录,next,链表,移除
From： https://blog.csdn.net/weixin_47681529/article/details/142220247

相关文章

  • 代码随想录算法训练营第四天|24两两交换链表中的节点 19删除链表的倒数第N个节点 02.0
    24.两两交换链表中的节点给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。由于今天赶时间，第一眼看完题目没思路就直接看文字解析了，但还是复述一下看完之后自己的理解/想法/思路。这一题感觉对......
  • 代码随想录Day2 | LeetCode 209. 长度最小的子数组、LeetCode 59. 螺旋矩阵 II、KamaC
    LeetCode209.长度最小的子数组子数组是一个连续的，很容易想到滑动窗口classSolution:defminSubArrayLen(self,target:int,nums:List[int])->int:windowSum=0left,right=0,0res=float('inf')whileright<len(nums......
  • [Python手撕]合并 K 个升序链表
    #Definitionforsingly-linkedlist.#classListNode:#def__init__(self,val=0,next=None):#self.val=val#self.next=nextclassSolution:defmergeKLists(self,lists:List[Optional[ListNode]])->Optional[ListNode]:......
  • 【算法竞赛】链表
    链表的特点是用一组位于任意位置的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以不连续。链表是容易理解和操作的基本数据结构,它的操作有初始化、添加、遍历、插入、删除、查找、释放等。链表分为单向链表和双向链表,如图所示.链表的各节点首尾相接,......
  • leetCode2：两数相加(链表)
    题目：给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字0之外，这两个数都不会以0开头。思路：遍历两个链表，逐位相加，还要加上进位结......
  • Leetcode 19.删除链表的倒数第第N个结点
    1.题目基本信息题目：给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。地址：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/2.解题方法2.1.解题思路使用快慢指针2.2.解题步骤第一步，初始化快指针为head，慢指针指向一个哑结点，哑结点......
  • 代码随想录算法训练营，9月17日 | 669. 修剪二叉搜索树，108.将有序数组转换为二叉搜索树，5
    669.修剪二叉搜索树题目链接：669.修剪二叉搜索树文档讲解︰代码随想录(programmercarl.com)视频讲解︰修剪二叉搜索树日期：2024-09-17想法：节点为空返回空，值在中间时，继续递归左右两边，小于时递归右子树，大于时递归左子树Java代码如下：classSolution{publicTreeNodetrimBST......
  • pta重排链表（一个很清晰的实现，完全模拟链表的实现）
    #include<iostream>#include<iomanip>#include<unordered_map>#include<string>usingnamespacestd;constintN=100010;unordered_map<string,string>neStr;unordered_map<string,int>eStr;stringheadStr;intn;......
  • 代码随想录Day15 动态规划--2
    01背包理论基础01背包是有一个背包有M的容量给我们N个物品每个物品有自己的价值我们需要装进背包里尽可能获得最大的价值分析题目把背包想象成一个二维数组先遍历每个物品放入背包里面dp数组的含义表示的就是背包所含有的价值当我们遍历物品1的时候我们要开始更新背包......
  • C# 链表排序之插入排序
    在C#中，对于链表（如LinkedList<T>）进行排序，插入排序是一个可行的选择，尽管它可能不是最高效的排序方法，特别是当链表很长时。插入排序的基本思想是将链表分成已排序和未排序的两部分，初始时，已排序部分只包含链表的第一个元素，然后依次将未排序部分的元素插入到已排序部分的适当位置......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99