行业知识
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很全面
上一篇:服务器领地红线怎么去掉?
下一篇:怎么加入多人服务器?