代码随想录算法训练营 Day 3
Published:
链表基础
Q1. LeetCode 203
解法1. 使用原链表
难点：需要考虑特殊情况：1. 头节点的值为val；2. 链表为空
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
while head and head.val == val:
head = head.next
if not head:
return head
curr = head
while curr.next:
temp = curr.next
if temp.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return head
解法2. 使用虚拟头节点（dummy head）
思路：在头节点之前创建一个虚拟节点，使得可以按照统一的方式进行操作
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_head = ListNode(next=head)
curr = dummy_head
while curr.next:
temp = curr.next
if temp.val == val:
curr.next = curr.next.next
else:
curr = curr.next
return dummy_head.next
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
Q2. LeetCode 707
思路：按照问题描述实现链表，用dummy_head实现可统一操作。注意各个函数中的特殊情况
class LinkNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_head = LinkNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
curr = self.dummy_head
while index >= 0:
curr = curr.next
index -= 1
return curr.val
def addAtHead(self, val: int) -> None:
new_head = LinkNode(val, self.dummy_head.next)
self.dummy_head.next = new_head
self.size += 1
def addAtTail(self, val: int) -> None:
curr = self.dummy_head
while curr.next:
curr = curr.next
new_tail = LinkNode(val)
curr.next = new_tail
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
# 判断标准不同，index可以为现有长度，即加在末尾
if index < 0 or index > self.size:
return
curr = self.dummy_head
while index:
curr = curr.next
index -= 1
new_node = LinkNode(val, curr.next)
curr.next = new_node
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
curr = self.dummy_head
while index:
curr = curr.next
index -= 1
curr.next = curr.next.next
self.size -= 1
Q3. LeetCode 206
解法1: 双指针法
思路：使用快慢指针，慢指针代表前一个节点，快指针代表当前节点。最后快指针会指向空值，而慢指针指向新的头节点，因此最后返回慢指针
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = None
fast = head
while fast:
# 获取下一个节点
temp = fast.next
# 反转当前节点和前一个节点
fast.next = slow
# 更新两个节点
slow = fast
fast = temp
return slow
解法2: 递归法
思路：类似于双指针法
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.reverse(None, head)
def reverse(self, prev, curr):
if curr == None:
return prev
temp = curr.next
curr.next = prev
return self.reverse(curr, temp)
解法3: 虚拟头节点
双指针法的另一种写法
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy_head = ListNode()
curr = head
while curr:
temp = curr.next
curr.next = dummy_head.next
dummy_head.next = curr
curr = temp
return dummy_head.next
复杂度分析
时间复杂度：O($n$) 空间复杂度：O(1)
总结
对于链表的问题，使用虚拟头节点可以统一操作，简化代码