移除链表元素

题意：删除链表中等于给定值 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]:
        dummy_head = ListNode(next = head)
        cur_node = dummy_head
        while cur_node.next:
            if cur_node.next.val == val:
                cur_node.next = cur_node.next.next
            else :
                cur_node = cur_node.next
        return dummy_head.next #关于为啥要.next,因为这个节点是我们创建的虚拟的，它指向的才是头节点

首先，在删除值为val的节点的时候我们要考虑头节点的情况，而且如果连续的多个节点等于val且在头节点的后面的时候，我们要用循环删去，总而言之，这种分类讨论的方法比较麻烦，为了解决这个问题我们可以采用虚拟头结点的方式。
创建虚拟头节点dummy_head，指向头节点head。
然后设置一个指针current，指向dummy_head。
遍历链表，当current.next的值等于val时，删除current.next节点，否则current指针后移。（循环条件用current.next，到达尾端的时候指向None，循环结束）
最后返回dummy_head.next，因为dummy_head本身是我们创造的虚拟的，而dummy_head.next才是真正的头节点。
解法二：不使用虚拟头节点

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

我只说我最开始没考虑的情况，例如111123，假设val=1，连续的1，当时我是用if的情况，条件满足头节点指向下一个，但是如果连续的val在头节点的后面，就会出错。
后面1233244441111232，我又用if，还是没删干净，我粘一下我的错误的代码，大家以此为戒，也可以看看我的错误代码思考我的问题。

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

设计链表

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

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

    def get(self, index: int) -> int:
        if index >= self.size or index < 0:   #为啥不能取等，类似数组下标从零开始
            return -1
        current = self.dummy_node.next # 有效节点从虚拟节点下一个开始
        for i in range(index):#这里循环用来找目标，链表的查找是要遍历的，不像数组用下标就行
            current = current.next
        return current.val

    def addAtHead(self, val: int) -> None:
        self.dummy_node.next = ListNode(val,self.dummy_node.next) #从右往左，先创建新的节点，且新节点的下个节点指向原来虚拟头的next，然后再让虚拟头指向新节点
        self.size += 1

    def addAtTail(self, val: int) -> None:
        current = self.dummy_node
        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 -1 
        current = self.dummy_node
        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_node
        for i in range(index):
            current = current.next
        current.next = current.next.next
        self.size -= 1

我做过卡码网的链表的基本操作，期末考完我把卡码网我做过的题也记录到这个blog里
额，就是index合法性检查，然后增加删除的基本操作

反转链表

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
方法一：双指针法

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        current = head
        while current:
            temp = current.next
            current.next = pre
            pre = current
            current = temp
        return pre

通过设置当前指针，pre指针来实现，每次循环都让当前指针指向前一个节点，然后pre指针移动到当前指针，当前指针移动到下一个节点，直到当前指针为空，返回pre指针。但是只是这样会丢失current.next的节点，因此需要temp指针来暂存current.next的节点，然后让current指针指向前一个节点，pre指针移动到current指针，current指针移动到temp指针，直到current指针为空，返回pre指针。

方法二：递归法

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.reverse(head,None)
    
    def reverse(self,current,pre) :
        if current == None:
            return pre
        temp = current.next
        current.next = pre
        return self.reverse(temp,current)

实话实话，让我再写一遍我写不出递归，我再捣鼓捣鼓吧，视频看懂了但又好像没看懂

代码随想录-day3

移除链表元素

设计链表

反转链表