颓废了5天，继续更新自己的学习之路qaq，真的好想摆啊，最近感觉活着好累(苦啊R1)，扯远了进正题吧
链表问题相对容易掌握。 不要忘记 "双指针解法" ，它不仅适用于数组问题，而且还适用于链表问题。还是直接上题目比较快（学过数据结构会发现链表其实也就那样，让我们把他拿下!）

算法一 删除链表中的节点

题目：
有一个单链表的 head，我们想删除它其中的一个节点 node。
给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。
链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。

自定义测试：
对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
我们将构建链表，并将节点传递给你的函数。
输出将是调用你函数后的整个链表。

一看就是课本老题目了，甚至期末还考了，下面直接给出完美课本解法（）两行直接搞定

解题方法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val=node.next.val
        node.next=node.next.next

算法题二 删除链表的倒数第N个节点

题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

解题方法一 双指针法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        # 创建虚拟头节点
        dummy.next = head
        
        # 初始化快慢指针
        fast = dummy
        slow = dummy
        
        # 快指针先移动 n 步
        for _ in range(n):
            fast = fast.next
        
        # 快慢指针同时移动，直到快指针到达链表末尾
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        # 删除倒数第 n 个节点
        slow.next = slow.next.next
        
        # 返回链表的头节点
        return dummy.next

解题方法二 递归

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # 定义一个递归函数，返回当前节点的倒数位置
        def dfs(node):
            if not node:
                return 0  # 到达链表末尾，返回 0
            count = dfs(node.next)  # 递归调用
            if count == n:  # 如果下一个节点是倒数第 n 个节点
                node.next = node.next.next  # 删除下一个节点
            return count + 1  # 返回当前节点的倒数位置

        # 如果删除的是头节点
        if dfs(head) == n:
            return head.next
        return head

算法三 反转链表

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

解法1

# 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: ListNode) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            next_node = curr.next  # 保存下一个节点
            curr.next = prev       # 反转当前节点的指针
            prev = curr            # 移动 prev 到当前节点
            curr = next_node       # 移动 curr 到下一个节点

        return prev  # prev 是新的头节点

算法4 合并两个有序链表

题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

我的思路是先相连后提取所有的val，之后重新赋值

解法一

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1:
            return l2
        if not l2:
            return l1

        # 连接两个链表
        current = l1
        while current.next:
            current = current.next
        current.next = l2

        # 提取所有节点的值
        values = []
        current = l1
        while current:
            values.append(current.val)
            current = current.next

        # 对值进行排序
        values.sort()

        # 重新赋值给新链表
        dummy = ListNode()
        current = dummy
        for val in values:
            current.next = ListNode(val)
            current = current.next

        return dummy.next

不过，这个解法不是很推荐，虽然很容易想到，因为：
缺点：
1.时间复杂度高：
提取所有节点的值需要遍历链表，时间复杂度为 O(n + m)。
对值进行排序的时间复杂度为 O((n + m) * log(n + m))。
重新赋值需要再次遍历链表，时间复杂度为 O(n + m)。
总时间复杂度为 O((n + m) * log(n + m))，比双指针法的 O(n + m) 更高。

2.空间复杂度高：
需要额外的空间存储所有节点的值，空间复杂度为 O(n + m)。
双指针法的空间复杂度仅为 O(1)。

3.破坏原链表结构：
连接链表会破坏原链表的结构，如果后续还需要使用原链表，可能会导致问题。

解法二 一般解法

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    # 创建一个虚拟头节点，方便操作
    dummy = ListNode()
    current = dummy
    
    # 遍历两个链表
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    
    # 如果其中一个链表还有剩余节点，直接接上
    if l1:
        current.next = l1
    else:
        current.next = l2
    
    # 返回合并后的链表头节点
    return dummy.next

时间复杂度：O(n + m)，其中 n 和 m 分别是两个链表的长度。我们需要遍历两个链表的所有节点。
空间复杂度：O(1)，我们只使用了常数级别的额外空间。
这个方法高效且易于理解，适用于大多数合并两个有序链表的场景。

算法五 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

如果是空间复杂度O(1)就不能取值比较哩，采用双指针秒吧

解题方法 双指针

# 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: ListNode) -> bool:
        arr = [] # 临时空间存储整个链表

        while head:
            arr.append(head.val)
            head = head.next

        # 使用双指针 
        left, right  = 0, len(arr) -1
        while left < right:
            if arr[left] != arr[right]:
                return False
            else:
                left += 1
                right -= 1
        return True
        # return arr == arr[::-1] # 方法2 使用Python 列表切片反转特性

吐槽一哈(共勉?maybe)

目前是2025年3月11日 星期二的23:17，明天就要提问单词了hhh，还没开始背，不过因为最近密码的太压抑了，想发泄一哈，写到算法笔记里面吧，首先这俩月我简直快疯了(苦啊R1yhtp QAQ)看着身边的朋友成功和幸福说不羡慕是假的，然后我也不知道要怎么办了，目前保研的希望估计是没了，然后想着卷卷技术考个研得了，可是就是提不起来劲，哎又伤心了()
分享一首歌，从我初识这首歌已经两年了，几乎平均一天一遍hhhh(当然是平均，有的时候一天循环几十遍)

https://music.163.com/#/song?id=30431366

希望未来一切安好，愿你我顶峰相见