相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
首次尝试
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode):
currentA = headA
while currentA is not None:
currentB = headB # 注意这里更新currentB
while currentB is not None:
if currentA is currentB: #注意这里比较地址
return currentA
currentB = currentB.next
currentA = currentA.next
return None问题
时间复杂度高：代码会导致时间复杂度为 O(m×n)，其中 m 和 n 是两个链表的长度。当两个链表很长时，这种方法效率低下。
改进
class Solution:
# 方法：双指针法
def getIntersectionNode(self, headA: ListNode, headB: ListNode):
if not headA or not headB:
return None
pointerA = headA
pointerB = headB
# 两个指针循环移动，直到相遇或到达链表尾部
while pointerA != pointerB:
# 如果 pointerA 遍历到链表结束，则从 headB 开始重新遍历
pointerA = pointerA.next if pointerA else headB
# 如果 pointerB 遍历到链表结束，则从 headA 开始重新遍历
pointerB = pointerB.next if pointerB else headA
# 返回相交的节点或者 None
return pointerA反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
双指针
代码
# 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]:
preNode = None
currentNode = head
# nextNode = None
while currentNode != None:
nextNode = currentNode.next
currentNode.next = preNode
preNode = currentNode
currentNode = nextNode
return preNode回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表
。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
首次尝试
遍历链表：
- 使用一个空列表
l1存储链表的值。 - 遍历链表，将每个节点的值添加到列表
l1中。
构造反转列表：
- 使用切片操作
l1[:]创建l2，这是原列表的副本。 - 调用
l2.reverse()将副本列表反转。
比较两个列表：
- 如果
l1和l2相等，说明链表是回文，返回True。 - 否则返回
False。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
l1 = []
currentNode = head
while currentNode != None:
l1.append(currentNode.val)
currentNode = currentNode.next
l2 = l1[:]
l2.reverse()
if l1 == l2:
return True
else:
return False复杂度
时间复杂度
- 遍历链表：遍历链表一次需要 O(n)，其中 n 是链表的长度。
- 列表反转：反转列表需要 O(n)。
- 列表比较：比较两个列表需要 O(n)。
总时间复杂度为 O(n)。
空间复杂度
额外空间：创建了两个列表 l1 和 l2，每个列表占用 O(n) 的空间。
总空间复杂度为 O(n)
改进
思路
- 找到链表的中间节点： 使用快慢指针（
slow和fast），slow每次走一步，fast每次走两步。当fast到达链表尾部时，slow恰好在链表的中间。 - 翻转后半部分链表： 从中间节点开始，将后半部分的链表翻转。翻转后，后半部分的链表会变成反向顺序。
- 比较前半部分和后半部分： 遍历翻转后的链表与原链表的前半部分，逐个比较节点的值。如果有任何值不相等，则返回
False；如果比较完成没有问题，则返回True。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 1. 找到链表的中间节点
slow = fast = head
while fast and fast.next:
slow = slow.next # 慢指针每次走一步
fast = fast.next.next # 快指针每次走两步
# 2. 翻转链表的后半部分
curNode = slow # 从中间节点开始翻转
preNode = None # 用于反转链表的前置节点
while curNode:
nextNode = curNode.next # 暂存下一节点
curNode.next = preNode # 当前节点指向前一个节点
preNode = curNode # 前置节点更新为当前节点
curNode = nextNode # 当前节点更新为下一节点
# 3. 比较链表的前半部分和翻转后的后半部分
# preNode 此时指向翻转后的链表头部
while preNode: # 遍历后半部分（长度较短）
if preNode.val != head.val: # 对应位置的值不相等
return False
preNode = preNode.next # 后半部分向前移动
head = head.next # 前半部分向前移动
# 4. 如果所有节点都匹配，返回 True
return True复杂度
- 时间复杂度：O(n)
- 找到中间节点 O(n/2)
- 翻转链表 O(n/2)
- 比较链表 O(n/2)
- 总体为 O(n)
- 空间复杂度：O(1)
- 没有使用额外的数据结构，翻转和比较操作均在链表本身完成。
参考
看到评论区有人说，如果链表长度是奇数，检查是否是回文时（
if (head->val != head2->val)），从head2开始的序列比head开始的序列要长。例如：[1, 2, 3, 4, 5]，按照大佬的实现，mid应该指向3，然后经过反转head2 = [5, 4, 3]，看起来比从head开始的序列[1, 2]还多一个。假如是这样的话，就算给定的是一个回文序列也会因为长度不同而判false吧？
实际上， reverseList 并没有砍断2到3之间的连接，而是“藕断丝连”被拉长了，所以head开始的序列应该是[1, 2, 3]（注意3的 next 已经被 reverseList 函数设为NULL了）