链表操作统一使用指向头节点的虚拟头节点dummy_head，并且初始化用于遍历链表的临时指针cur=dummy_head，要操作的节点位于cur的下一个节点

链表移除元素

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_node=ListNode(next=head) #虚拟头节点，指向真实头节点
        current = dummy_node # 当前节点初始化为虚拟头节点
        while(current.next is not None):
            if (current.next.val==val):
                current.next=current.next.next # 删除节点
            else:
                current=current.next # 不删除节点，继续遍历

        return dummy_node.next #注意返回的是头节点

设计链表

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

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。

addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。

addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。

addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

注意在index处操作节点，cur需要初始化为dummyhead
也就是对于在某处删除和插入操作，cur的下一个节点才是操作的节点，循环终止的条件也就是下一个节点是需要操作的节点,对于遍历循环的跳出条件，可以取特殊值0思考。

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>self.size-1 or index<0:
            return -1
        cur = self.dummyhead.next # 从头节点开始遍历
        for i in range(index):
            cur=cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.size+=1
        cur=self.dummyhead.next #因为是在头节点前添加，所以操作头节点即可
        newhead=ListNode(val=val,next=cur)
        self.dummyhead.next=newhead


    def addAtTail(self, val: int) -> None:
        self.size+=1
        cur=self.dummyhead #self.dummyhead.next应该也可以，因为是遍历到最后一个
        newtail=ListNode(val=val)
        while(cur.next is not None):#遍历到尾节点
            cur=cur.next
        cur.next=newtail


    def addAtIndex(self, index: int, val: int) -> None:
        '''在第index节点前插入一个节点'''
        if index<0 or index>self.size-1:
            return
        self.size+=1
        newnode= ListNode(val=val)
        cur=self.dummyhead #注意是初始化为虚拟头节点
        while(index):#循环结束的条件是下一个节点是第index个节点
            cur=cur.next
            index-=1
        newnode.next = cur.next #新节点指向插入节点
        cur.next = newnode #插入节点前一个节点指向


    def deleteAtIndex(self, index: int) -> None:
        '''删除第index个节点'''
        if index<0 or index>self.size-1:
            return
        self.size-=1
        cur=self.dummyhead
        while(index):#循环结束的条件是下一个节点是第index个节点
            cur=cur.next
            index-=1
        #删除节点就是让被删除节点的前一个节点指向被删除节点的下一个节点
        cur.next=cur.next.next 


# 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)

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表头。题目链接

双指针法

使用
“`pre`和`cur“`两个指针在每次循环中`pre`指向`cur`，反转每个节点的指向。循环的终止条件是`cur`指向空

# 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]:
        #双指针法
        pre=None 
        cur=head #初始化为头节点
        while(cur is not None):#循环终止条件是cur指向空
            temp=cur.next #保存cur的下一个节点用于更新cur
            cur.next=pre #反转指向
            # 更新两个指针，一定要先移动pre
            pre=cur
            cur=temp
        #循环结束的时候cur指向空，pre指向原有尾节点（也即反转后的头节点）
        return pre

递归法

用双指针的思路实现，先暂存cur.next，改变cur指针指向，再更新pre和cur指针。

# 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]:
        #递归法
        pre=None
        cur=head

        def reverse(pre,cur):
            if (cur is None):#递终止条件
                return pre
            temp=cur.next
            cur.next=pre
            return reverse(cur,temp) #归

        return reverse(pre,cur)