一.相交链表
1.题目
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交：
2.题解
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pA=headA
pB=headB
while pA!=pB:
pA=pA.next if pA else headB
pB=pB.next if pB else headA
return pA二.反转链表
1.题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
2.题解
方法一：笨方法 反转存储到列表里，再根据这个列表新建一个链表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
vals=[]
pA=head
while pA:
vals.append(pA.val)
pA=pA.next
vals=vals[::-1]
if not vals:#避免空值导致后面访问空值越界
return None
dummy=ListNode(vals[0])#创建第一个节点
head2=dummy #创建头指针
for val in vals[1:]:#从第一个值开始而不是第0个
head2.next=ListNode(val)
head2=head2.next
return dummy
方法二：直接反转链表方向 (头插）
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reverseList(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
pre=None
cur=head
while cur:
nxt=cur.next
cur.next=pre
pre=cur
cur=nxt
return pre
三.判断回文链表
1.题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1] 输出：true
2.题解
回文链表反转存储在列表【】中
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def isPalindrome(self, head):
"""
:type head: Optional[ListNode]
:rtype: bool
"""
vals=[]
while head:
vals.append(head.val)
head=head.next
return vals==vals[::-1]
四.链表排序
1.题目
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
2.题解
链表不同与数组，因为有方向，所以和数组排序能用很多方法不同，比较适合的就是归并排序。
这里是学习的灵神的方法：在刚开始学习积累的时候，建议在B站先看灵神的解读【反转链表【基础算法精讲 06】-哔哩哔哩】 https://b23.tv/63r1l12，先不看代码，自己写，然后看题解。
class Solution:
# 876. 链表的中间结点（快慢指针）
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
pre = slow # 记录 slow 的前一个节点
slow = slow.next
fast = fast.next.next
pre.next = None # 断开 slow 的前一个节点和 slow 的连接
return slow
# 21. 合并两个有序链表（双指针）
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() # 用哨兵节点简化代码逻辑
while list1 and list2:
if list1.val < list2.val:
cur.next = list1 # 把 list1 加到新链表中
list1 = list1.next
else: # 注：相等的情况加哪个节点都是可以的
cur.next = list2 # 把 list2 加到新链表中
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2 # 拼接剩余链表
return dummy.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 如果链表为空或者只有一个节点，无需排序
if head is None or head.next is None:
return head
# 找到中间节点 head2，并断开 head2 与其前一个节点的连接
# 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
head2 = self.middleNode(head)
# 分治
head = self.sortList(head)
head2 = self.sortList(head2)
# 合并
return self.mergeTwoLists(head, head2)
整体是一个递归的思想，这个sortList函数首先把一个链表一分为二（采用快慢指针找链表中点，然后断开中点和后面一个节点的连接）。然后对这个被分成两段的链表，要得到它们的排序新链表，也要调用sortList函数，直到递归到只有一个节点或者空节点，就不用排序了。
（1）把链表递归一分为二
（2）递归直到分到最小，返回合并后的，一层层全部合并完，在合并的过程中完成了排序。
时间复杂度：O(nlogn) 空间复杂度：O(logn)[递归的深度]
五.合并两个有序链表
1.题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
2.题解
这个题就是上面链表排序使用归并方法题的一部分
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
cur = dummy = ListNode() # 用哨兵节点简化代码逻辑
while list1 and list2:
if list1.val < list2.val:
cur.next = list1 # 把 list1 加到新链表中
list1 = list1.next
else: # 注：相等的情况加哪个节点都是可以的
cur.next = list2 # 把 list2 加到新链表中
list2 = list2.next
cur = cur.next
cur.next = list1 or list2 # 拼接剩余链表
return dummy.next