链表经典问题
1.反转链表
问题：将链表反转，并返回新的头节点。
思路：设置两个指针，反别表示现节点和前节点，遍历链表，同时设置一个临时指针储存下一个节点。然后让现指针的next指向前指针。
def reverseList(self, head):
cur = head
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
最后前节点pre即为新的头节点。
2.移除链表元素
问题：移除给出链表中的元素等于val的节点，并返回。
(1)递归
思路：函数先判断除头节点外的节点，不断调用该函数，使得找到末节点。当链表为空时返回，对于每个函数中头节点进行判断，如果节点的值等于val则返回head.next，相当于将该节点删除，返回剩下的节点，如果不等则返回该节点，即没有删除。直到最后对真正的头节点进行判断，递归结束。
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if not head:
return
head.next = self.removeElements(head.next,val)
return head.next if head.val == val else head
(2)迭代
思路：设置一个指针，使他的next指向头节点。遍历链表，不断对指针的下一个节点进行判断，如果节点值等于val，则使指针的next指向next.next，就实现的删除。由于可能会删除头节点，所以需要设置一个哑节点使他的next指向真正头节点
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummyhead = ListNode()
dummyhead.next = head
temp = dummyhead
while temp.next:
if temp.next.val == val:
temp.next = temp.next.next
else:
temp = temp.next
return dummyhead.next
(3)双指针
思路：设置两个指针分别表示前一个节点和现在的节点，遍历链表当节点的值等于val时，判断节点的位置，分别进行不同的删除操作。因为保存的前一个节点，所以删除操作会简单很多。
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
cur = head
pre = None
while cur:
if cur.val == val:
if cur == head:
head = cur.next
cur = head
elif cur.next == None:
pre.next = None
break
else:
cur = cur.next
pre.next = cur
else:
pre = cur
cur = cur.next
return head
3.奇偶链表
问题：给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
思路：先分别建立两个新链表，设置两个指针，表示奇数项节点和偶数项节点，遍历链表。指针每次走两个节点，表示都为奇数项或都为偶数项。最后让偶数链表的头节点与奇数链表的末节点相连。
注意：要先设置变量保存偶数项链表的头节点，如果想用head.next的方法访问是不行的，因为head现在与偶数项的头节点无关，head.next指向原来的head.next.next。
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
evenhead = head.next
odd = head
even = head.next
while odd.next and even.next:
odd.next = odd.next.next
even.next = even.next.next
odd = odd.next
even = even.next
odd.next = evenhead
return head
4.回文链表
问题：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false
有以下三种方法
(1)列表
思路：建立一个列表来储存链表的值，再反转列表，如果反转后相等则为回文链表。
def isPalindrome(self, head: Optional[ListNode]) -> bool:
l = []
temp = head
while temp:
l.append(temp.val)
temp = temp.next
r = l.copy()
r.reverse()
return r == l
(2)迭代
思路:先设置一个指针指向头节点位于递归函数外，再设置递归函数。递归不断找到与递归函数外指针对称的节点，判断是否相等，不相等返回Flase。同时如果相等，则递归函数外指针往前进一个节点，即指向它的next。简单来说就是先判断头节点和末节点是否相等，然后分别前进和后退一个节点再进行判断。
def isPalindrome(self, head: Optional[ListNode]) -> bool:
self.head = head
def check(cur = head):
if cur:
if not check(cur.next): #这一行保证只要递归函数的一层不相等，就整个函数返回False
return False
if cur.val != self.head.val:
return False
self.head = self.head.next
return True
return check()
(3)快慢指针
思路：设置快慢指针，快指针一次走两个节点，慢指针一次走一个节点。当快指针走完整个链表时，慢指针刚好走到链表的中间节点。然后对慢指针之后的链表进行反转，再与反转前的链表进行对比，如果不等就返回False，否则返回True。
def isPalindrome(self, head: Optional[ListNode]) -> bool:
self.fast = self.slow = temp = head
while self.fast.next and self.fast.next.next:
self.fast = self.fast.next.next
self.slow = self.slow.next
self.slow = self.reverse(self.slow)
while self.slow and temp:
if temp.val != self.slow.val:
return False
temp = temp.next
self.slow = self.slow.next
return True
def reverse(self,head):
cur = head
pre = None
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre