LeetCode203:移除链表元素
题目
题目链接:203:移除链表元素
方法一:
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)
提示:
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:反转链表
方法一:双指针法
#这部分定义了一个单链表的节点类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
递归函数是在函数定义中调用自身的函数。换句话说,递归函数是通过不断调用自身来解决问题的一种方法。文章来源地址https://www.toymoban.com/news/detail-578467.html
到了这里,关于力扣python刷题day03|LeetCode203、707、206的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!