前言

今天是算法训练营开营第三天，今天白天的表现有点近似浅浅给自己放了个假（实际就是很懈怠），一整天只干了完成训练营任务一件事，希望后续不要再懈怠下来了。

今天的内容主要是链表部分开了个头，链表部分的内容在我大二刚学的时候就掌握得不是很好，如今重新回顾最大感触就是后悔当初怎么没直接看卡尔的文章巩固链表部分hh，今天的题目总体感觉还是比较简单的，大体上把链表相关的概念和基础操作巩固了一下。

203.移除链表元素

题目链接：203. 移除链表元素

题目描述：

删除链表中等于给定值 val 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2： 输入：head = [], val = 1 输出：[]

示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

思路

这道题目总体来说还是比较简单的，考验链表的基本操作，在实现上主要有两种方式：不引入虚拟头节点（哨兵节点）和引入虚拟头节点。如果不引入虚拟头节点，我们在移除元素时需要考虑当前节点是否是头节点，头节点和非头节点的删除操作存在差别（因为执行删除操作时，我们的当前节点是被删除节点的前面一个节点）。出于便利性考虑，这边我选择使用引入虚拟头节点的做法，引入一个虚拟头节点，然后让虚拟头节点持续指向实际的头节点，这样我们要删除头节点时只需要让当前节点为虚拟头节点就行。后面的操作就是比较简单，判断当前节点的下一个节点数值是否与目标值相等，如果相等就执行链表删除的操作。

实现写法

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummyHead = ListNode(next = head)
        current = dummyHead
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        return dummyHead.next

707.设计链表

题目链接：707. 设计链表

题目描述：

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

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

思路

这道题的主要内容大致是实现链表的所有基本操作，虽然每一个操作的实际操作步骤大概都能想到，但是在实际落地执行的时候总是出现循环次数设置不当的问题（大概改了四版才改完）。

这边记录每次修改的重点问题：

1️⃣

 def get(self, index: int) -> int:
        if index < 0 or index > self.size:
  			#修正：索引范围应该是[0, size - 1]
 				#修改为：
 def get(self, index: int) -> int:
        if index < 0 or index >= self.size:

2️⃣

for i in range(index):
  cur = cur.next
  #修正：应当移动到第index个节点，现在是index-1（因为dummyHead是虚拟头节点）
 	#修改为
for i in range(index+1):
  cur = cur.next

实现写法：

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

class MyLinkedList:
    def __init__(self):
        self.dummyHead = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        else:
            cur = self.dummyHead
            for i in range(index + 1):
                cur = cur.next
            return cur.val

    def addAtHead(self, val: int) -> None:
        self.dummyHead.next = ListNode(val, self.dummyHead.next)
        self.size += 1

    def addAtTail(self, val: int) -> None:
        cur = self.dummyHead
        while cur.next:
            cur = cur.next
        cur.next = ListNode(val, None)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        cur = self.dummyHead
        if index > self.size:
            return
        elif index == self.size:
            self.addAtTail(val)
        elif index <= 0:
            self.addAtHead(val)
        else:    
            for i in range(index):
                cur = cur.next
            cur.next = ListNode(val, cur.next)
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        cur = self.dummyHead
        if index >= 0 and index < self.size:
            for i in range(index):
                cur = cur.next
            cur.next = cur.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)

循环执行index次，实际上是移动到第index-1个节点位置，一定要记得！！！

206.反转链表

题目链接：206. 反转链表

题目描述：

反转一个单链表。

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

思路

这道题实际上思路上也比较简单理解，主要干的事情就是，定义两个指针：cur和pre，cur用来执行更新和记录当前节点，pre是用来反转的关键，记录cur的前一个节点，并且pre初始为None。接下来要做的事情就比较简单了，从头向后依次操作，用temp记录下当前节点的下一个节点，再用cur.next = pre来反转当前节点，最后更新pre为cur再让cur为temp来到下一个节点。

直接实现写法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        pre = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

递归实现写法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)
    def reverse(self, cur: ListNode, pre: ListNode):
        if cur == None:
            return pre
        temp = cur.next
        cur.next = pre
        pre = cur
        return self.reverse(temp,pre)

这道题的递归相较于其他情况下的递归更容易理解一些

总结

在算法训练营第三天的题目里，我们主要学习了链表的基本概念和对于链表的基本操作，在写链表基本操作逻辑时，需要时刻注意index范围问题和加入虚拟头节点后index的实际循环次数。