1、反转链表
leetcode206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
首先认识链表这种结构：
class Listnode:
def _init_(self,x):
self.val=x
self.next=None
思路：
保存为数组，反转数组，新产生一个链表，注意返回的链表要指向反转数组产生的链表
代码如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
l=[]
while head:
l.append(head.val)
head=head.next
l.reverse()
if len(l)==0:
return None
result=ListNode(l[0])
result1=ListNode(l[0])
result1=result
k=len(l)
for i in range(1,k):
result.next=ListNode(l[i])
result=result.next
return result1
实现反转以及上一个节点变成当前节点
（1）将节点指向关系改变
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre=None
cur=head
while cur:
tmp=cur.next
cur.next=pre
pre=cur
cur=tmp
return pre
2、相交链表
leetcode160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
思路：对齐两个链表
代码如下：
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
h1=headA
h2=headB
while h1 != h2:
if h1:
h1=h1.next
else:
h1=headB
if h2:
h2=h2.next
else:
h2=headA
return h1
3、合并两个有序的链表
leetcode21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
思路：判断大小，然后将有序添加到一个新的链表中，注意返回结果是指向新链表的next
代码如下：
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
node=ListNode()
res=node
while l1 and l2:
if l1.val<=l2.val:
node.next=l1
l1=l1.next
node=node.next
else:
node.next=l2
l2=l2.next
node=node.next
if l1:
node.next=l1
if l2:
node.next=l2
return res.next
4、回文链表
leetcode234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
思路1:遍历产生数组，看数组倒序后是否和愿数组相同，时间和空间复杂度都为O(n)
代码如下：
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
vals = []
cur=head
while cur:
vals.append(cur.val)
cur=cur.next
return vals==vals[::-1]
5、环形链表
leetcode141. 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
思路：把节点存在字典或者集合中，再次出现说明有环。
代码如下：
class Solution:
def hasCycle(self, head: ListNode) -> bool:
seen = {}
while head:
if head in seen:
return True
seen[head]=1
head = head.next
return False
