链表操作统一使用指向头节点的虚拟头节点dummy_head，并且初始化用于遍历链表的临时指针cur=dummy_head，要操作的节点位于cur的下一个节点
两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。题目链接
cur初始化在dummyhead，指向头节点
1. 每次交换前需要存储本次循环的”1号”和”3号”节点。
temp = cur.next
temp1 = cur.next.next.next
- 再按照三个步骤执行交换。注意**指向这个操作是
“`所操作节点.next = xxx`**- cur指向2号节点
cur.next=cur.next.next - 2号节点指向存储好的1号节点
cur.next.next = temp - 1号节点指向存储好的3号节点
cur.next.next.next = temp1
- cur指向2号节点
- 最后移动cur指针指向两个节点后（
cur=cur.next.next）
循环的终止条件是cur的下两个节点均不为空（可以囊括链表节点个数是奇数和偶数的情况）while(cur.next!=None and cur.next.next!=None)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode(next=head)
cur = dummyhead
while(cur.next != None and cur.next.next!= None):#适用于奇数和偶数的终止条件
temp = cur.next #存储1号节点
temp1 = cur.next.next.next #存储3号节点
cur.next = cur.next.next #step1. cur指向2号节点
cur.next.next = temp #step2. 2号节点指向1号节点
cur.next.next.next = temp1 #step3. 1号节点指向3号节点
cur=cur.next.next #移动current
return dummyhead.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)