力扣-链表相关题 持续更新中。。。。。。
一.相交链表
1.题目
在力扣平台上的问题页面中解决相交链表问题
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交**：**[
](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png)
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
python
二.反转链表
1.题目
206. 逆转链表 - 力扣（LeetCode）
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 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
python
方法二：直接反转链表方向 (头插）
# 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
python
三.判断回文链表
1.题目
给定单链表的头节点 head ，请判定该链表是否为回文链表。如果是，则返回 true ；否则返回 false 。
示例 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 isPalindrome(self, head):
"""
:type head: Optional[ListNode]
:rtype: bool
"""
vals=[]
while head:
vals.append(head.val)
head=head.next
return vals==vals[::-1]
python
四.链表排序（确定链表中点-使用快慢法, 整合两个有序链式结构-使用快慢法, 采用分治法-将问题拆分为两半）
1.题目
148号题：排序链表问题 - 力扣（LeetCode）
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
**输入：****输出：**2.题解
链表与数组的不同之处在于存在指向性。由于存在指向性，不能采用与之类似的排序方法。归并排序正是最适合的选择。
反转链表【基础算法精讲 06
反转链表【基础算法精讲 06
这里记录的是灵神的学习方法：当刚开始进行知识积累时
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)
python
该函数首先采用快慢指针方法将链表分成两部分；然后对这两段分别进行排序操作时仍需调用该函数；这一过程会持续进行直至处理单个节点或空链表为止
（1）把链表递归一分为二
（2）递归直至分到最小层次，在最终返回所有层次的有序结果；整个过程实现了有序排列
时间复杂度：O(nlogn) 空间复杂度：O(logn)[递归的深度]
五.合并两个有序链表
1.题目
合并两个有序链表 - 力扣（LeetCode）
实现两个有序链表的合并，并在完成后返回一个有序的新链表。生成的新有序链表是由这两个列表的所有节点按顺序重新组合而成。
示例 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 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
python
写透快慢指针的方法：
六.找链表的中间节点
1.题目
第876题：链式数据结构中的中点节点问题 - 力扣（LeetCode）
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示例 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 middleNode(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
fast=slow=head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
return slow
python
七.环形链表
1.题目
给你一个链表的头节点 head ，判断链表中是否有环。
如果一个链表中的某个节点可以通过持续追踪 next 指针最终再抵达同一个节点，则该链表中存在一个环。 为了标识给定链表中存在的循环（即环），系统内部使用整数 pos 来表示循环尾部连接到该循环中的位置（索引从 0 开始）。请注意：pos 并未作为函数或方法的参数传递。这一设置仅用于清晰标识循环的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
**输入：****输出：****解释：**2.题解
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
fast=slow=head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if slow==fast:
return True
return False
python
八.环形链表II
1.题目
[142. 环状链表问题 II - LeetCode](https://leetcode.cn/problems/linked-list-cycle-ii/description/?envType=study-plan-v2&envId=top-100-liked "142. 环状链表问题 II - LeetCode)
对于链表的头节点 head ，被确定为入环点的那个节点即为目标点。当该链表不存在循环时，则返回 null。
2.题解
相较于环形I题而言，本题不仅需要判别是否存在回路这一要素，并且还需确定节点的具体位置
二级结论：当快慢指针相遇的时候，慢指针还没有走完一整圈
推导：
上面推导出来的公式说明：
除了双指针之外还另外单独添加了一个head指针这一做法是基于推导得出其公式特性的结果
在相遇点之后，slow继续前进C的距离时，在相遇点之后的位置上。此时 fast 与相遇点之间的距离变为 a - c = (k - 1)(b + c)，即等于环长的整数倍。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
fast=slow=head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if slow==fast:
while slow is not head:
slow=slow.next
head=head.next
return slow
python
