一、203.移除链表元素
关键点：如何删除节点，需要知道删除节点前的节点。
1、无虚拟头节点的方法
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
while head != None and head.val == val: # 如果头节点的值为 val
head = head.next
cur = head
while cur:
if cur.next != None and cur.next.val == val: # 需要删除一个节点，需要知道前一个节点。所以这里判断是否删除 cur.next 指向节点
cur.next = cur.next.next
else:
cur = cur.next
return head
2、带虚拟头节点
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy_node = ListNode(next=head)
cur = dummy_node
while cur:
if cur.next and cur.next.val == val: # 一样的删除节点需要知道前一个节点
cur.next = cur.next.next
else:
cur = cur.next
return dummy_node.next
总结: 涉及到链表删除的题，都使用一个虚拟头节点。因为需要判断头节点是否被删除了。
二、707.设计链表
关键点:涉及到删除和添加，设置一个虚拟头节点，方便操作。设置一个 self.size 方便进行 index 和 size 的判断。
class LinkNode:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
self.dummy_node = LinkNode()
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index > self.size - 1:
return -1
cur = self.dummy_node.next
for _ in range(index):
cur = cur.next
return cur.val
def addAtHead(self, val: int) -> None:
add_node = LinkNode(val)
add_node.next = self.dummy_node.next # 画图看下面一行代码和这一行代码谁在前面
self.dummy_node.next = add_node
self.size += 1
def addAtTail(self, val: int) -> None:
tail_node = LinkNode(val)
cur = self.dummy_node
while cur.next: # 连接最后一个节点，需要知道前一个节点
cur = cur.next
cur.next = tail_node
self.size += 1
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return
index_node = LinkNode(val)
cur = self.dummy_node
while index:
cur = cur.next
index -= 1
index_node.next = cur.next
cur.next = index_node
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index > self.size - 1:
return
cur = self.dummy_node
while index:
cur = cur.next
index -= 1
cur.next = cur.next.next
self.size -= 1
三、206.反转链表
关键点：画图移动指针
双指针
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
pre, cur = None, head
while cur: # 画图可知 cur 为 None 时退出循环
tmp = cur.next # 临时变量 tmp 记录下 cur.next 的节点
cur.next = pre # cur 节点指向 pre
pre = cur # pre 移动到 cur
cur = tmp # cur 移动到 cur.next
return pre
递归
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur, pre = head, None
return self.reverse(cur, pre)
# 递归反转 2 个节点之间的指向
def reverse(self, cur, pre):
if not cur:
return pre
# 记录下一个要交换指向的节点
tmp = cur.next
# 进行节点指向交换
cur.next = pre
# 移动指针指向
pre = cur
cur = tmp
return self.reverse(cur, pre)