力扣python刷题day03|LeetCode203、707、206

这篇具有很好参考价值的文章主要介绍了力扣python刷题day03|LeetCode203、707、206。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

LeetCode203:移除链表元素

题目

题目链接:203:移除链表元素
力扣python刷题day03|LeetCode203、707、206,python,leetcode,开发语言,链表

方法一:

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head=ListNode(next=head)
        current=dummy_head
        while current.next:
            if current.next.val==val:
                current.next=current.next.next
            else:
                current=current.next
        return dummy_head.next

知识点:

设置虚拟头结点

LeetCode707:设计链表

题目

来源:力扣(LeetCode)
力扣python刷题day03|LeetCode203、707、206,python,leetcode,开发语言,链表
力扣python刷题day03|LeetCode203、707、206,python,leetcode,开发语言,链表提示:

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

方法一:单链表法

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)

LeetCode206:反转链表

题目:

来源:206:反转链表

力扣python刷题day03|LeetCode203、707、206,python,leetcode,开发语言,链表

方法一:双指针法

#这部分定义了一个单链表的节点类ListNode,具有一个val属性表示节点的值,以及一个next属性表示指向下一个节点的指针。

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

#Solution类包含一个reverseList方法,它接收一个头节点head作为参数,并返回反转后的链表的头节点。
#首先,创建两个指针cur和pre,分别初始化为头节点head和None。cur指针用于遍历链表,pre指针用于保存反转后的链表。
#接下来,使用while循环遍历链表,直到cur指针为空(即遍历到链表的末尾)为止。
#在每一次循环中,首先保存当前节点cur的下一个节点到临时变量temp中,因为接下来要修改cur的next指针。
#然后,将当前节点cur的next指针指向前一个节点pre,实现节点的反转。
#接着,更新pre和cur指针的位置,将pre指向当前节点cur,将cur指向下一个节点temp。
#重复以上步骤,直到遍历完整个链表。
#最后,当循环结束时,返回反转后的链表的头节点pre。
#这段代码通过不断地将当前节点的next指针指向前一个节点,从而实现了链表的反转操作。它使用了迭代而非递归的方式,将链表从前往后进行遍历和修改,最终得到反转后的链表。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head   
        pre = None
        while cur:
            temp = cur.next # 保存一下 cur的下一个节点,因为接下来要改变cur->next
            cur.next = pre #反转
            #更新pre、cur指针
            pre = cur
            cur = temp
        return pre

方法二:递归法

#这部分定义了一个单链表的节点类ListNode,它具有一个val属性表示节点的值,以及一个next属性表示指向下一个节点的指针。

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

#Solution类包含一个reverseList方法,它接收一个头节点head作为参数,并返回反转后的链表的头节点。它调用了另一个名为reverse的辅助方法,将head节点和None(反转链表的尾节点)作为参数传递给它。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode) -> ListNode:
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        return self.reverse(temp, cur)

#reverse方法是一个递归函数,它接收两个参数:当前节点cur和前一个节点pre。它的目的是将以cur节点为头节点的子链表反转,并返回反转后的链表的头节点。
#首先,它检查当前节点是否为None。如果是,说明已经遍历完整个链表,返回反转后的链表的头节点pre。
#否则,它创建一个临时变量temp来存储下一个节点(即当前节点的后继节点)。然后,它将当前节点的next指针指向前一个节点pre,完成了节点的反转操作。
#接下来,递归调用reverse方法,将temp作为新的当前节点,将cur作为新的前一个节点传递进去。这样就可以对剩余的子链表进行反转。
#最终,当递归返回到最初的调用处时,reverseList方法将返回反转后的链表的头节点。
#这段代码利用递归的方式不断将当前节点的指针指向前一个节点,从而实现了链表的反转操作。

知识点:

首先定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。
然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。
为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。
接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。
最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。

递归函数是在函数定义中调用自身的函数。换句话说,递归函数是通过不断调用自身来解决问题的一种方法。文章来源地址https://www.toymoban.com/news/detail-578467.html

到了这里,关于力扣python刷题day03|LeetCode203、707、206的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 看完这篇文章你就彻底懂啦{保姆级讲解}-----(LeetCode刷题203.707.206翻转链表) 2023.4.21

    本文章一部分内容参考于《代码随想录》----如有侵权请联系作者删除即可,撰写本文章主要目的在于记录自己学习体会并分享给大家,全篇并不仅仅是复制粘贴,更多的是加入了自己的思考,希望读完此篇文章能真正帮助到您!!! 力扣题目链接 关于这个算法思想,我在之

    2024年02月04日
    浏览(53)
  • Day03|链表01:203.移除链表元素、707.设计链表、206.反转链表

    今天进入链表章节的学习了,也是之前学过的内容,这次争取快速AC。 leetcode链接:https://leetcode.cn/problems/remove-linked-list-elements/ 没什么好说的,这里注意引入了一个虚拟头节点dummy,这样就不用处理需要删除第一个节点的特殊情况。删除时C++需要手动detete。我本来使用free的,

    2024年02月17日
    浏览(43)
  • 代码随想录第三天|链表理论基础,LeetCode203.移除链表元素, LeetCode707.设计链表,LeetCode 206.反转链表

    链表: 链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是head。 链表类型: 1.单链表 单链表中的指

    2024年02月11日
    浏览(52)
  • 力扣 [203、707、206]

    创建新链表:自己的 创建新的链表: 定义一个新的头指针,并且将该指针指向一个空节点。 再定义一个当前指针,负责指向新链表的尾节点。之所以要让当前指针始终指向尾节点,是为了下次方便增添新的元素加入队列。 再定义一个遍历指针,负责对于原链表的遍历和检验

    2024年02月16日
    浏览(33)
  • day 3 | 203.移除链表元素、707.设计链表、206.反转链表

    目录: 链表基础:https://programmercarl.com/链表理论基础.html 题目链接: https://leetcode.cn/problems/remove-linked-list-elements/ 203. 移除链表元素 给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点  。 自己思路:从头

    2024年02月08日
    浏览(43)
  • 【代码随想录刷题记录】 203.移除链表元素 、 707.设计链表 、206.反转链表

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

    2024年02月08日
    浏览(47)
  • Day 3 链表: 203.移除链表元素, 707.设计链表, 206.反转链表

    链接基础,以及链表和数组的区别: 代码随想录 1. 链表类型: 单列表,双列表,循环列表。 单列表: 双列表: 循环列表: 2. 链表的操作 :删除节点,增加节点。 删除节点: 其中对于 普通的节点 删除,就如上图所示,直接让前一个节点的指向下一个节点即可。 但是对于

    2024年02月16日
    浏览(41)
  • day3_203移除链表元素_707设计链表_206反转链表

    链表是一种通过指针串联起的线性结构,每个节点由两部分组成: 一个数据域,一个指针域(存放指向下一节点的指针),最后一个节点的指针域指向null。 链表入口节点是头结点head。 双链表:两个指针域,指向下一节点和上一节点。( 向前向后查询) 循环链表:首尾相连

    2024年02月16日
    浏览(33)
  • 代码随想录day3 | 203.移除链表元素 707.设计链表 206.反转链表

    直接让前一个节点指向后一个节点即可 两种方法 第一种:直接删除 第二种:头删的时候,直接 head=head-next 其实这两种方法都没有做到统一 第三种:虚拟头结点法 这样的话,咱们删除的时候,就是以统一的规则来进行删除啦! 203.移除链表元素 法一:原始删除法 1、while(h

    2024年02月16日
    浏览(39)
  • day3-链表理论基础 203.移除链表元素 707.设计链表 206.反转链表

    单链表 双链表:每个节点有两个指针域,一个指向下一个节点,一个指向上一个节点 既可以查询前一个节点,又能查询后一个节点 循环列表:链表首尾相连 在内存上 不是连续分布 的,散乱分布在内存中的某地址上 删除节点:next指针直接指向下下个节点,且在内存中删除

    2024年02月04日
    浏览(34)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包