小工具知识网

当前位置: 首页 > 行业知识 > Python - 代码随想录算法训练营第三天 | LeetCode203 移除链表元素、LeetCode707 设计链表、LeetCode206 反转链表

行业知识

Python - 代码随想录算法训练营第三天 | LeetCode203 移除链表元素、LeetCode707 设计链表、LeetCode206 反转链表

2026-11-21 07:23:26 来源:互联网转载

代码随想录算法训练营第三天 | LeetCode203 移除链表元素、LeetCode707 设计链表、LeetCode206 反转链表

  • 前言
  • 一、 LeetCode203 移除链表元素
  • 二、LeetCode707 设计链表
  • 三、LeetCode206 反转链表
  • ���结

    前言

    Python 完成以上问题:

    以下是链表在python中的写法

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

    一、 LeetCode203 移除链表元素

    力扣题目链接(opens new window)

    题意:反转一个单链表。

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

    # Definition for singly-linked list.# class ListNode:#     def __init__(self, val=0, next=None):#         self.val = val#         self.next = nextclass Solution:    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:        #虚拟节点        dummy_head = ListNode(next = head)        corrent = dummy_head        #开始在链表中遍历        while corrent.next:            if corrent.next.val == val:                corrent.next = corrent.next.next            else:                corrent = corrent.next        return dummy_head.next

    二、LeetCode707 设计链表

    题意:

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

    get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。

    addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。

    addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。

    addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。

    deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

    这道题目设计链表的五个接口:

    获取链表第index个节点的数值

    在链表的最前面插入一个节点

    在链表的最后面插入一个节点

    在链表第index个节点前面插入一个节点

    删除链表的第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 = 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  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 = 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 = nextclass MyLinkedList:    def __init__(self):        self.head = None        self.tail = None        self.size = 0    def get(self, index: int) -> int:        if index = self.size:            return -1                if index  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  self.size:            return                if index == 0:            self.addAtHead(val)        elif index == self.size:            self.addAtTail(val)        else:            if index  None:        if 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  

    三、LeetCode206 反转链表

    力扣题目链接(opens new window)

    题意:反转一个单链表。

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

    # Definition for singly-linked list. # class ListNode: #     def __init__(self, val=0, next=None): #         self.val = val #         self.next = nextclass Solution:    def rev'''erseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        current = head        pre = None        while current:            temp = current.next            current.next = pre            pre = current            current = temp        return pre

    感觉很奇怪,在IDLE里跑不出来,Leetcode就可以


    总结

    链表有思路,但不会用python写,707很全面

上一篇:服务器领地红线怎么去掉?

下一篇:怎么加入多人服务器?