链表

Problems

LeetCode 0002 两数相加 (中等, 2021-10)
LeetCode 0019 删除链表的倒数第N个结点 (中等, 2022-01)
LeetCode 0025 K个一组翻转链表 (困难, 2022-02)
LeetCode 0086 分隔链表 (中等, 2021-10)
LeetCode 0143 重排链表 (中等, 2022-01)
LeetCode 0876 链表的中间结点 (简单, 2022-01)
剑指Offer 0600 从尾到头打印链表 (简单, 2021-11)
剑指Offer 1800 删除链表的节点 (简单, 2021-11)
剑指Offer 2200 链表中倒数第k个节点 (简单, 2021-11)
剑指Offer 2400 反转链表 (简单, 2021-11)
剑指Offer 2500 合并两个排序的链表 (简单, 2021-11)
剑指Offer 3500 复杂链表的复制（深拷贝） (中等, 2021-12)
剑指Offer 5200 两个链表的第一个公共节点 (简单, 2022-01)
牛客 0002 重排链表 (中等, 2022-01)
牛客 0003 链表中环的入口结点 (简单, 2022-01)
牛客 0004 判断链表中是否有环 (简单, 2022-01)
牛客 0021 链表内指定区间反转 (中等, 2022-01)
牛客 0023 划分链表 (中等, 2022-01)
牛客 0024 删除有序链表中重复的元素-II (中等, 2022-01)
牛客 0025 删除有序链表中重复的元素-I (中等, 2022-01)
牛客 0033 合并两个排序的链表 (简单, 2022-02)
牛客 0040 链表相加(二) (中等, 2022-03)
牛客 0050 链表中的节点每k个一组翻转 (中等, 2022-03)
牛客 0066 两个链表的第一个公共结点 (简单, 2022-03)
牛客 0070 单链表的排序 (简单, 2022-03)

`LeetCode 0002 两数相加 (中等, 2021-10)`

问题简述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

详细描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：
    输入：l1 = [2,4,3], l2 = [5,6,4]
    输出：[7,0,8]
    解释：342 + 465 = 807.

示例2：
    输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Python

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


class Solution:

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:  # noqa
        ret = p = ListNode()

        s = 0
        # 注意遍历条件，当三个都不为真时才会结束
        while l1 or l2 or s != 0:  # s != 0 表示最后一次相加存在进位的情况
            s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

            p.next = ListNode(s % 10)  # 个位
            p = p.next

            # 遍历链表
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

            s = s // 10  # 进位

        return ret.next

`LeetCode 0019 删除链表的倒数第N个结点 (中等, 2022-01)`

问题简述

给定链表，删除链表的倒数第 n 个结点，返回删除后链表的头结点。

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

详细描述

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

示例 1：
    输入：head = [1,2,3,4,5], n = 2
    输出：[1,2,3,5]
示例 2：
    输入：head = [1], n = 1
    输出：[]
示例 3：
    输入：head = [1,2], n = 1
    输出：[1]

提示：
    链表中结点的数目为 sz
    1 <= sz <= 30
    0 <= Node.val <= 100
    1 <= n <= sz

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Python

# 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: ListNode, n: int) -> ListNode:

        dummy = ListNode(0)  # 伪头节点
        dummy.next = head

        k = n + 1  # 获取倒数第 n+1 个节点
        lp, fp = dummy, dummy
        while fp:
            if k <= 0:
                lp = lp.next
            
            fp = fp.next
            k -= 1
        
        # print(lp.val)
        lp.next = lp.next.next
        return dummy.next

`LeetCode 0025 K个一组翻转链表 (困难, 2022-02)`

问题简述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：
    你可以设计一个只使用常数额外空间的算法来解决此问题吗？
    你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

25. K 个一组翻转链表 - 力扣（LeetCode）

思路

每次用 l, r 两个指针框定需要翻转的范围，完成翻转后继续下一组，直到最后一组不足 k 个节点结束；
注意节点的拼接；

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        # 翻转一个子链表
        def reverse(l, r):
            pre, cur = None, l
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt

            return r, l  # 翻转后，头尾交换

        dummy = ListNode(0)  # 因为头结点可能会变，设置一个伪头结点
        dummy.next = head

        pre = dummy  # pre 定位在 l 的前面
        l = head
        while l:
            r = pre  # r 初始化为上一个节点，这样走 k 步后正好划定一个 [l, r] 的闭区间
            for _ in range(k):
                r = r.next
                if not r:
                    return dummy.next
            
            nxt = r.next
            r.next = None  # 切断，这里是否切断要看具体的 reverse 是怎么实现的，这里的实现需要切断
            l, r = reverse(l, r)
            pre.next = l  # 重新接入链表
            r.next = nxt
            
            # [l, r] 翻转完成后，继续下一组 [l, r]
            pre = r  # pre 初始化为上一组的 r
            l = r.next  # l 初始化为上一组 r 的下一个节点
        
        return dummy.next

`LeetCode 0086 分隔链表 (中等, 2021-10)`

问题描述

快排链表的核心操作；

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：
    输入：head = [1,4,3,2,5,2], x = 3
    输出：[1,2,2,4,3,5]
示例 2：
    输入：head = [2,1], x = 2
    输出：[1,2]
 
提示：
    链表中节点的数目在范围 [0, 200] 内
    -100 <= Node.val <= 100
    -200 <= x <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

新建两个链表，分别保存小于 x 和大于等于 x 的，最后拼接；

Python3

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        """"""
        # l/r 会进行移动，lo/hi 为头节点
        l = lo = ListNode(0)
        r = hi = ListNode(0)
        
        while head:
            if head.val < x:  # 小于 x 的拼到 lo
                l.next = head
                l = l.next
            else:  # 大于等于 x 的拼到 hi
                r.next = head
                r = r.next
                
            head = head.next
        
        # 因为不能保证最后遍历的节点在 hi 中，所以必须加上这一步，切断循坏
        r.next = None  # 关键步骤
        l.next = hi.next
        
        return lo.next

`LeetCode 0143 重排链表 (中等, 2022-01)`

问题简述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

详细描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：
    输入：head = [1,2,3,4]
    输出：[1,4,2,3]
示例 2：
    输入：head = [1,2,3,4,5]
    输出：[1,5,2,4,3]

提示：
    链表的长度范围为 [1, 5 * 104]
    1 <= node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：模拟

先找到中间节点 mid；
将链表 mid 反转；
然后合并 head 和 mid；

Python：写法1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
    
        def  get_mid(p):
            lp, fp = p, p

            while fp and fp.next:
                lp = lp.next
                fp = fp.next.next
            
            return lp
        
        def reverse(p):
            cur, pre = p, None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            return pre
        
        mid = get_mid(head)  # 注意此时还没有断开两个链表
        mid = reverse(mid)

        # merge
        l, r = head, mid
        while True:
            l_nxt, r_nxt = l.next, r.next
            if not r_nxt:  # 这是一种写法，另一种写法是在获得 mid 后将 mid 与原链表断开（后移一个节点，结果也是正确的，见写法2）
                break
            l.next, r.next = r, l_nxt
            l, r = l_nxt, r_nxt

Python：写法2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
    
        def  get_mid(p):
            lp, fp = p, p

            while fp and fp.next:
                lp = lp.next
                fp = fp.next.next
            
            return lp
        
        def reverse(p):
            cur, pre = p, None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            return pre
        
        mid = get_mid(head)
        mid.next, mid = None, mid.next  # 写法2）提前断开 mid
        # mid, mid.next = mid.next, None  # err
        mid = reverse(mid)

        # merge
        l, r = head, mid
        while r:
            l_nxt, r_nxt = l.next, r.next
            # if not r_nxt:
            #     break
            l.next, r.next = r, l_nxt
            l, r = l_nxt, r_nxt

`LeetCode 0876 链表的中间结点 (简单, 2022-01)`

问题简述

给定非空链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

详细描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：
    输入：[1,2,3,4,5]
    输出：此列表中的结点 3 (序列化形式：[3,4,5])
    返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
    注意，我们返回了一个 ListNode 类型的对象 ans，这样：
    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
    输入：[1,2,3,4,5,6]
    输出：此列表中的结点 4 (序列化形式：[4,5,6])
    由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：
    给定链表的结点数介于 1 和 100 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/middle-of-the-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：快慢指针

Python

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

        lp, fp = head, head
        while fp and fp.next:
            fp = fp.next.next
            lp = lp.next
        
        return lp

`剑指Offer 0600 从尾到头打印链表 (简单, 2021-11)`

问题简述

从尾到头打印链表（用数组返回）

详细描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
    输入：head = [1,3,2]
    输出：[2,3,1]

限制：
    0 <= 链表长度 <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

法1）利用栈，顺序入栈，然后依次出栈即可
法2）利用深度优先遍历思想（二叉树的先序遍历）

Python：栈

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

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        
        # ret = []
        # for _ in range(len(stack)):  # 相当于逆序遍历
        #     ret.append(stack.pop())
        # return ret
        return stack[::-1]  # 与以上代码等价

Python：DFS、递归

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

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        if head is None:
            return []

        ret = self.reversePrint(head.next)
        ret.append(head.val)

        return ret

`剑指Offer 1800 删除链表的节点 (简单, 2021-11)`

问题简述

给定单向链表的头节点和要删除的节点的值（链表中的值都不相同），返回删除后链表的头节点。

详细描述

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:
    输入: head = [4,5,1,9], val = 5
    输出: [4,1,9]
    解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
    输入: head = [4,5,1,9], val = 1
    输出: [4,5,9]
    解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：
    题目保证链表中节点的值互不相同
    若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

一般有两种写法：
1. 单独处理头结点；
2. 建立伪头结点，原头结点跟普通节点一样处理（推荐）

Python：写法1

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

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val:  # 头结点单独处理
            return head.next

        cur = head  # 记录当前遍历的节点
        while cur:
            pre = cur  # 记录 cur 的前一个节点
            cur = cur.next
            if cur.val == val:  # 移除匹配的节点
                pre.next = cur.next
                break
        
        return head

Python：写法2

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

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head

        pre = dummy  # 记录 cur 的前一个节点
        cur = dummy.next  # 记录当前遍历的节点
        while cur:
            if cur.val == val:  # 移除匹配的节点
                pre.next = cur.next
                break
            pre = cur  
            cur = cur.next
        
        return dummy.next

`剑指Offer 2200 链表中倒数第k个节点 (简单, 2021-11)`

问题简述

输入一个链表，输出该链表中倒数第k个节点。

详细描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：
    给定一个链表: 1->2->3->4->5, 和 k = 2.
    返回链表 4->5.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

前后双指针，保持两个指针相距 k 个节点，当前指针达到链表尾时，返回后指针；

Python

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

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        if head is None or k < 1:
            return head

        cur = head
        ret = head

        while k:
            cur = cur.next
            k -= 1
        
        while cur:
            ret = ret.next
            cur = cur.next

        # 更简洁的写法，合并两个循环
        # while cur:
        #     if k <= 0: 
        #         ret = ret.next
        #     cur = cur.next
        #     k -= 1

        return ret

`剑指Offer 2400 反转链表 (简单, 2021-11)`

问题简述

输入一个链表的头节点，反转该链表。

详细描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

限制：
    0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

Python：递归（写法1）

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

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:
        if not head:  # 单独处理空链表
            return head
        
        self.ret = None

        def dfs(cur):
            # nonlocal ret  # 如果不使用 self.ret，而是 ret，就需要加上这句
            
            if cur.next is None:
                if self.ret is None:
                    self.ret = cur  # 尾节点，即新链表的头节点
                return cur
            
            nxt = dfs(cur.next)
            nxt.next = cur
            return cur
        
        
        head = dfs(head)
        head.next = None  # 断开最后一个节点，容易忽略的一步
        return self.ret

Python：递归（写法2）

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

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:

        def dfs(cur, pre):  # 当前节点，上一个节点
            if cur is None:  # 达到尾结点
                return pre  # 返回尾结点的上一个节点
            
            ret = dfs(cur.next, cur)
            cur.next = pre  # 把当前节点的 next 指向上一个节点
            return ret
        
        return dfs(head, None)

Python：迭代

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            # 注意顺序
            nxt = cur.next # 暂存后继节点 cur.next
            cur.next = pre # 修改 next 引用指向
            pre = cur      # pre 暂存 cur
            cur = nxt      # cur 访问下一节点
        return pre

`剑指Offer 2500 合并两个排序的链表 (简单, 2021-11)`

问题简述

合并两个有序链表，且合并后依然有序；

详细描述

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：
    输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

限制：
    0 <= 链表长度 <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：递归

递归公式：merge(l1, l2) = li + merge(li.next, lj)，
其中当 l1<l2 时 i,j = 1,2，否则 i,j=2,1

Python

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

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        
        def dfs(p1, p2):
            if not p1: return p2
            if not p2: return p1

            if p1.val < p2.val:
                p1.next = dfs(p1.next, p2)
                return p1
            else:
                p2.next = dfs(p1, p2.next)
                return p2

        return dfs(l1, l2)

思路2：迭代

合并两个排序的链表（伪头节点，清晰图解）

Python：伪头结点（推荐）

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ret = cur = ListNode(0)

        while l1 and l2:
            if l1.val < l2.val:
                cur.next, l1 = l1, l1.next
            else:
                cur.next, l2 = l2, l2.next
            
            cur = cur.next  # 这一步容易忽略
        
        cur.next = l1 if l1 else l2
        return ret.next

Python：不使用伪头结点

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1

        cur = ret = l1 if l1.val < l2.val else l2  # 
        
        while l1 and l2:
            if l1.val < l2.val:  # 这两处的判断条件要一致，否则会出错
                cur.next, l1 = l1, l1.next
            else:
                cur.next, l2 = l2, l2.next
            cur = cur.next
        
        cur.next = l1 if l1 else l2
        return ret

`剑指Offer 3500 复杂链表的复制（深拷贝） (中等, 2021-12)`

问题简述

复制带随机指针的链表，返回复制后链表的头结点；

详细描述

注意：本题的输入输出带有迷惑性，它们并不是实际的输入和输出，而是链表的数组展现；

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：
    输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
    输入：head = [[1,1],[2,1]]
    输出：[[1,1],[2,1]]
示例 3：
    输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]
示例 4：
    输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

提示：
    -10000 <= Node.val <= 10000
    Node.random 为空（null）或指向链表中的节点。
    节点数目不超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1：哈希表

先看下普通链表的复制：

普通链表的复制

    class Solution:
        def copyList(self, head: 'Node') -> 'Node':
            cur = head
            ret = pre = Node(0)  # 伪头结点
            while cur:
                node = Node(cur.val) # 复制节点 cur
                pre.next = node      # 新链表的 前驱节点 -> 当前节点
                # pre.random = '???' # 新链表的 「 前驱节点 -> 当前节点 」 无法确定
                cur = cur.next       # 遍历下一节点
                pre = node           # 保存当前新节点
            return ret.next

首先要理解本题的难点：
- 复制当前节点的时候，随机指针指向的节点可能还没有创建；
- 即使你先按普通链表先把节点都创建出来，由于链表无法随机访问的性质，你也不知道随机节点在哪个位置；
解决方法是利用哈希表（写法1）：
- 第一次遍历时，记录每个节点对应的复制节点；
- 第二次遍历时，根据原链表的指向从哈希表中提取对应的节点，建立指向关系；
本题还有一种递归的写法（写法2）：
- 同样用一个哈希表保存

Python：迭代（写法1）

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None  # 使用伪头结点，可以省去这行

        dp = dict()

        # 第一次遍历，生成复制节点，并记录到哈希表
        p = head
        while p:
            dp[p] = Node(p.val)
            p = p.next
        
        # 写法1：使用伪头结点，可以省去对 head 为 None 的判断
        cur = head
        ret = pre = Node(0)  # 伪头结点
        while cur:
            pre.next = dp[cur]  # 这里可以不用 get，因为一定存在
            pre.next.random = dp.get(cur.random)  # get 方法在 key 不存在时，默认返回 None
            cur = cur.next
            pre = pre.next

        return ret.next

        # 写法2：相比使用伪头结点
        # cur = head
        # while cur:
        #     dp[cur].next = dp.get(cur.next)
        #     dp[cur].random = dp.get(cur.random)
        #     cur = cur.next
        
        # return dp[head]

Python：递归（写法2）

【不推荐】虽然代码量会少一点，但是不好理解；

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None

        dp = dict()
        
        def dfs(p):
            if not p: return None

            if p not in dp:
                dp[p] = Node(p.val)
                dp[p].next = dfs(p.next)
                dp[p].random = dfs(p.random)
        
            return dp[p]
        
        return dfs(head)

思路2：复制+拆分

详见：复杂链表的复制（哈希表 / 拼接与拆分，清晰图解）

注意这个方法需要遍历三次：
- 第一次复制节点
- 第二次设置随机节点
- 第三次拆分
因为随机节点指向任意，所以必须先设置完所有随机节点后才能拆分；

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None

        # 复制节点
        cur = head
        while cur:
            nod = Node(cur.val)  # 创建节点
            cur.next, nod.next = nod, cur.next  # 接入新节点
            cur = nod.next  # 遍历下一个节点

        # 设置随机节点，因为随机节点指向任意，所以必须先设置随机节点后才能断开
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 拆分节点
        cur = head
        ret = nxt = head.next
        while nxt.next:
            # 开始拆分
            cur.next = cur.next.next
            nxt.next = nxt.next.next

            # 下一组
            cur = cur.next
            nxt = nxt.next
        
        return ret

`剑指Offer 5200 两个链表的第一个公共节点 (简单, 2022-01)`

问题描述

输入两个链表，找出它们的第一个公共节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1

两个链表的第一个公共节点（差值法） - 宫水三叶

分别遍历两个链表，得到两个链表的长度，记为 l1 和 l2；
让较长的先走 |l1 - l2| 步，然后一起走，第一个相同节点即为公共节点；

Python

# 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) -> ListNode:

        def get_list_len(p):
            cnt = 0
            while p:
                p = p.next
                cnt += 1
            
            return cnt

        la = get_list_len(headA)
        lb = get_list_len(headB)

        if la > lb:
            p1, p2 = headA, headB
        else:
            p1, p2 = headB, headA

        c = abs(la - lb)
        while c:
            p1 = p1.next
            c -= 1

        while p1 != p2:
            p1 = p1.next
            p2 = p2.next

        return p1

思路2

两个链表的第一个公共节点 - Krahets

本质上跟思路1 是类似的，但是更巧妙，写法也更简洁；
把 headA 和 headB 都分为两段，记 headA = la + lc，headB = lb + lc，其中 lc 为公共部分；
对指针 pa，当遍历完 headA 后紧接着遍历 headB；指针 pb 和 headB 同理，那么遍历过程如下：
```
headA -> headB = la -> lc -> lb -> lc
headB -> headA = lb -> lc -> la -> lc
```
因为 la + lc + lb == lb + lc + la，当 pa 和 pb 遍历完这三段时，接下去的第一个节点就是公共节点；
如果 lc 部分的长度为 0，那么公共节点就是 NULL；

Python

# 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) -> ListNode:
        
        pa, pb = headA, headB
        while pa != pb:
            # 如果两个链表没有公共节点，循环结束时，pa == pa == None
            pa = pa.next if pa else headB
            pb = pb.next if pb else headA
        
        return pa

`牛客 0002 重排链表 (中等, 2022-01)`

问题简述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
    L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
    L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

重排链表_牛客题霸_牛客网

思路：模拟

先找到中间节点 mid；
将链表 mid 反转；
然后合并 head 和 mid；

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head: return
    
        def  get_mid(p):
            lp, fp = p, p

            while fp and fp.next:
                lp = lp.next
                fp = fp.next.next
            
            return lp
        
        def reverse(p):
            cur, pre = p, None
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            
            return pre
        
        mid = get_mid(head)  # 注意此时还没有断开两个链表
        mid = reverse(mid)

        # merge
        l, r = head, mid
        while True:
            l_nxt, r_nxt = l.next, r.next
            if not r_nxt:  # 这是一种写法，另一种写法是在获得 mid 后将 mid 与原链表断开（后移一个节点，结果也是正确的，见写法2）
                break
            l.next, r.next = r, l_nxt
            l, r = l_nxt, r_nxt

`牛客 0003 链表中环的入口结点 (简单, 2022-01)`

问题简述

给一个长度为 n 的链表，若其中包含环，请找出该链表的环的入口结点，否则返回null。

链表中环的入口结点_牛客题霸_牛客网

思路：快慢指针

快指针 fast 每次走两步，慢指针 slow 每次走一步；
若存在环，则 fast 与 slow 必会相遇；
相遇后，将 slow 重新指向 pHead，然后，双指针正常每次走一步；
当再次相遇时，即为入口节点；
注意无环的情况；

证明：

假设存在环，记环之前的节点数即为 $a$（不包括入口节点），环的节点数为 $b$；当 fast 和 slow 相遇时距离环入口的步数为 $c$；
下面证明：$a=c$
记 fast 和 slow 走的步数分别为 $f$ 和 $s$，且 $f-s = nb$，即 fast 比 slow 多走了 n 圈；又 $f=2s$，可得 $s=nb$，而实际上 slow 走的距离 $s=a + (n-1)b + (b-c)$，联立得 $a=c$；
因此当 fast 和 slow 在环内相遇时，将 slow 重新指向 pHead，然后双指针再次相遇时即为入口节点（每次走一步）；

Python

class Solution:
    def EntryNodeOfLoop(self, pHead: ListNode):
        # write code here

        no_cycle = True
        slow = fast = pHead
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                no_cycle = False
                break

        if no_cycle:
            return None

        slow = pHead
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return slow

`牛客 0004 判断链表中是否有环 (简单, 2022-01)`

问题简述

判断给定的链表中是否有环。

判断链表中是否有环_牛客题霸_牛客网

思路：快慢指针

Python

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

#
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        
        fast = slow = head
        has_cycle = False
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                has_cycle = True
                break
        
        return has_cycle

`牛客 0021 链表内指定区间反转 (中等, 2022-01)`

问题简述

给定链表 head，把 m 到 n 区间内的节点反转

链表内指定区间反转_牛客题霸_牛客网

思路：模拟

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        
        # 增加一个伪头结点，主要针对完全反转的情况
        dummy = ListNode(0)
        dummy.next = head
        
        cnt = n - m
        pre, cur = dummy, head
        while m - 1:  # 因为要保存开始反转之前的一个节点，所以少移动一次
            m -= 1
            pre = cur
            cur = cur.next
        
        beg, end = pre, cur
        pre, cur = cur, cur.next  # 把少移动的一次补回来
        
        # 开始反转，反转 cnt 次
        while cnt:
            cnt -= 1
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        # 重新拼接（可以画图理解为什么是这两个位置拼接）
        beg.next = pre
        end.next = cur
        
        return dummy.next

`牛客 0023 划分链表 (中等, 2022-01)`

问题简述

给定链表和一个值 x，将所有小于 x 的值移动到左侧，保持相对顺序；

划分链表_牛客题霸_牛客网

思路

快排中的 partition 操作；
因为链表的特殊性，扩展链表并不会带来额外的消耗；
考虑维护两个链表，分别保存小于 x 的节点和其他节点；最后将两个链表拼接即可；
此外还有一种基于双指针的思路：
- 考虑左指针有右指针，开始时，直接将右指针移动到末尾，然后遍历左指针，遇到大于等于 x 的节点就移动到右指针的位置；

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param x int整型 
# @return ListNode类
#
class Solution:
    def partition(self , head: ListNode, x: int) -> ListNode:
        # write code here
        
        small = l = ListNode(0)
        large = r = ListNode(0)
        
        cur = head
        while cur:
            if cur.val < x:
                l.next = cur
                l = l.next
            else:
                r.next = cur
                r = r.next
            cur = cur.next
        
        l.next = large.next
        r.next = None
        return small.next

`牛客 0024 删除有序链表中重复的元素-II (中等, 2022-01)`

问题简述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
    给出的链表为 1→2→3→3→4→4→5, 返回 1→2→5.
    给出的链表为 1→1→1→2→3, 返回 2→3.

删除有序链表中重复的元素-II_牛客题霸_牛客网

思路见代码

链表问题的核心是保证 pre、cur、nxt 三个指针的关系正确；
此外，使用任何节点的值之前要确保该节点不为空；

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        
        dummy = ListNode(0)
        dummy.next = head
        
        pre, cur = dummy, head
        while cur:
            nxt = cur.next
            if nxt and cur.val == nxt.val:  # 找到相等值的范围（闭区间）
                while nxt.next and nxt.val == nxt.next.val:
                    nxt = nxt.next
                # 退出循环时，nxt 指向的相同值的最后一个，所以下面要用 nxt.next
                pre.next = cur = nxt.next
            else:
                pre, cur = cur, nxt
        
        return dummy.next

`牛客 0025 删除有序链表中重复的元素-I (中等, 2022-01)`

问题简述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为 1→1→2, 返回 1→2.
给出的链表为 1→1→2→3→3, 返回 1→2→3.

删除有序链表中重复的元素-I_牛客题霸_牛客网

思路

因为要保留范围内的第一个节点，因此可以省略 pre；

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        
        cur = head
        while cur:
            nxt = cur.next
            if nxt and nxt.val == cur.val:
                while nxt.next and nxt.val == nxt.next.val:
                    nxt = nxt.next
                cur.next = nxt.next
            cur = cur.next
        
        return head

`牛客 0033 合并两个排序的链表 (简单, 2022-02)`

问题简述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

合并两个排序的链表_牛客题霸_牛客网

思路

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        
        dummy = cur = ListNode(0)
        
        p1, p2 = pHead1, pHead2
        while p1 and p2:
            if p1.val < p2.val:
                cur.next = p1
                p1 = p1.next
            else:
                cur.next = p2
                p2 = p2.next
            cur = cur.next
        
        cur.next = p1 if p1 else p2
        
        return dummy.next

`牛客 0040 链表相加(二) (中等, 2022-03)`

问题简述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。

链表相加(二)_牛客题霸_牛客网

思路1：转成数值计算（超时）

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        
        def get_v(cur):
            ret = 0
            while cur:
                ret = ret * 10 + cur.val
                cur = cur.next
            return ret
        
        s = get_v(head1) + get_v(head2)
        s = str(s)

        dummy = cur = ListNode(0)
        for c in s:
            cur.next = ListNode(int(c))
            cur = cur.next
            
        return dummy.next

思路2：利用栈

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        # write code here
        
        def get_v(x):
            ret = []
            while x:
                ret.append(x.val)
                x = x.next
            return ret
        
        h1 = get_v(head1)
        h2 = get_v(head2)
        
        ret = []
        ex = 0
        while h1 or h2:
            h1v = h1.pop() if h1 else 0
            h2v = h2.pop() if h2 else 0
            v = h1v + h2v + ex
            ret.append(v % 10)
            ex = v // 10
        
        if ex:
            ret.append(1)
            
        dummy = cur = ListNode(0)
        while ret:
            cur.next = ListNode(ret.pop())
            cur = cur.next
            
        return dummy.next

思路3：反转链表后逐位相加（推荐）

Python

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head1 ListNode类 
# @param head2 ListNode类 
# @return ListNode类
#
class Solution:
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        
        # def pp(x):
        #     """打印链表（调试用）"""
        #     tmp = []
        #     while x:
        #         tmp.append(x.val)
        #         x = x.next
        #     print(tmp)
        
        def reverse(x):
            """反转链表"""
            pre, cur = None, x
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
                
            return pre
        
        h1 = reverse(head1)
        h2 = reverse(head2)
        
        cur = dummy = ListNode(0)
        ex = 0  # 进位
        
        # 合并 h1 和 h2 的判断
        while h1 or h2:
            h1v = h1.val if h1 else 0
            h2v = h2.val if h2 else 0
            v = h1v + h2v + ex
            node = ListNode(v % 10)
            ex = v // 10
            cur.next = node
            cur = cur.next
            h1 = h1.next if h1 else None
            h2 = h2.next if h2 else None
        
        # 将下面两段合并到一起
        # ex = 0
        # while h1 and h2:
        #     v = h1.val + h2.val + ex
        #     node = ListNode(v % 10)
        #     ex = v // 10
        #     cur.next = node
        #     cur = cur.next
        #     h1 = h1.next
        #     h2 = h2.next
         
        # h = h1 if h1 else h2
        # while h:
        #     v = h.val + ex
        #     node = ListNode(v % 10)
        #     ex = v // 10
        #     cur.next = node
        #     cur = cur.next
        #     h = h.next
        
        # 如果还存在进位
        if ex:
            cur.next = ListNode(1)
        
        ret = dummy.next
        return reverse(ret)  # 注意最后再反转一次

`牛客 0050 链表中的节点每k个一组翻转 (中等, 2022-03)`

问题简述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

链表中的节点每k个一组翻转_牛客题霸_牛客网

思路（不使用栈）

每次取 k 个节点，反转后接入原链表；
细节很多，不容易写对，详见代码；

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        dummy = ListNode(0)
        dummy.next = head
        
        def reverse(h):
            """标准的反转链表"""
            pre, cur = None, h
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            return pre, h  # 反转后的首尾节点
        
        # [l, r] 分别指向子链表的首尾节点，
        # 小技巧，把 r 初始化为 l 的前一个节点，那么移动 k 次后，就刚好是第 k 个节点
        pre = dummy 
        l, r = head, pre
        while l:
            for _ in range(k):
                r = r.next
                if not r:  # 不足 k 个节点，提前返回
                    return dummy.next
            
            # 断开 r 和 r.next 就是一个标准的链表反转；否则需要调整尾结点的判断，不推荐
            nxt, r.next = r.next, None
            l, r = reverse(l)  # 得到反转后的首尾节点
            pre.next, r.next = l, nxt  # 接入原链表
            pre, l = r, nxt   # 更新下一组 pre, l, r；
            # 因为反转后 r 刚好就是下一组 l 的前一个节点，所以不用再更新
        
        return dummy.next

`牛客 0066 两个链表的第一个公共结点 (简单, 2022-03)`

问题简述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

两个链表的第一个公共结点_牛客题霸_牛客网

思路1：计算长度差

计算两个链表的长度差 d；让长的链表先走 d 步；

Python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        
        def get_len(cur):
            cnt = 0
            while cur:
                cnt += 1
                cur = cur.next
            return cnt
        
        l1 = get_len(pHead1)
        l2 = get_len(pHead2)
        
        if l1 < l2:
            return self.FindFirstCommonNode(pHead2, pHead1)
        
        cur1, cur2 = pHead1, pHead2
        
        d = l1 - l2
        while d:
            cur1 = cur1.next
            d -= 1
        
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        
        return cur1

思路2：拼接两个链表

Python

class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        
        c1, c2 = pHead1, pHead2
        while c1 != c2:
            c1 = c1.next if c1 else pHead2
            c2 = c2.next if c2 else pHead1
        
        return c1

`牛客 0070 单链表的排序 (简单, 2022-03)`

问题简述

给定一个节点数为n的无序单链表，对其按升序排序。

单链表的排序_牛客题霸_牛客网

思路1：归并排序

细节：
- 找中点的时候，定位到中点的前一个位置，保存中点位置后切断，否则会无限循环；
- 递归的 base case：最好判断为空节点或只有一个节点时就返回；

Python

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        
        def merge(h):
            if not h or not h.next: return h
            
            # 找中点
            f, s = h.next, h
            while f and f.next:
                f = f.next.next
                s = s.next
            
            # 切断
            m, s.next = s.next, None
            l, r = merge(h), merge(m)
            
            # 合并
            cur = dummy = ListNode(0)
            while l and r:
                if l.val < r.val:
                    cur.next = l
                    l = l.next
                else:
                    cur.next = r
                    r = r.next
                cur = cur.next
            
            cur.next = l if l else r
            return dummy.next
        
        return merge(head)

思路2：快排（超时）

链表的快排比数组好写一点，因为链表可以方便的移动节点，而不需要要交换；
默认使用头结点作为 pivot，因此部分用例无法通过（超过最大递归）；
对链表来说似乎没有很好的办法来确定 pivot；

Python

class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        
        import sys
        sys.setrecursionlimit(1000000)
        
        def qsort(h):
            if not h or not h.next: return h
            
            s = small = ListNode(0)
            l = large = ListNode(0)
            cur = h.next
            while cur:
                if cur.val <= h.val:
                    s.next = cur
                    s = s.next
                else:
                    l.next = cur
                    l = l.next
                cur = cur.next
            
            s.next = h
            h.next = l.next = None
            
            small = qsort(small.next)
            large = qsort(large.next)
            h.next = large
            
            return small
        
        ret = qsort(head)
        return ret

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

数据结构-链表.md

数据结构-链表.md

链表

Problems

`LeetCode 0002 两数相加 (中等, 2021-10)`

`LeetCode 0019 删除链表的倒数第N个结点 (中等, 2022-01)`

`LeetCode 0025 K个一组翻转链表 (困难, 2022-02)`

`LeetCode 0086 分隔链表 (中等, 2021-10)`

`LeetCode 0143 重排链表 (中等, 2022-01)`

`LeetCode 0876 链表的中间结点 (简单, 2022-01)`

`剑指Offer 0600 从尾到头打印链表 (简单, 2021-11)`

`剑指Offer 1800 删除链表的节点 (简单, 2021-11)`

`剑指Offer 2200 链表中倒数第k个节点 (简单, 2021-11)`

`剑指Offer 2400 反转链表 (简单, 2021-11)`

`剑指Offer 2500 合并两个排序的链表 (简单, 2021-11)`

`剑指Offer 3500 复杂链表的复制（深拷贝） (中等, 2021-12)`

`剑指Offer 5200 两个链表的第一个公共节点 (简单, 2022-01)`

`牛客 0002 重排链表 (中等, 2022-01)`

`牛客 0003 链表中环的入口结点 (简单, 2022-01)`

`牛客 0004 判断链表中是否有环 (简单, 2022-01)`

`牛客 0021 链表内指定区间反转 (中等, 2022-01)`

`牛客 0023 划分链表 (中等, 2022-01)`

`牛客 0024 删除有序链表中重复的元素-II (中等, 2022-01)`

`牛客 0025 删除有序链表中重复的元素-I (中等, 2022-01)`

`牛客 0033 合并两个排序的链表 (简单, 2022-02)`

`牛客 0040 链表相加(二) (中等, 2022-03)`

`牛客 0050 链表中的节点每k个一组翻转 (中等, 2022-03)`

`牛客 0066 两个链表的第一个公共结点 (简单, 2022-03)`

`牛客 0070 单链表的排序 (简单, 2022-03)`

Files

数据结构-链表.md

Latest commit

History

数据结构-链表.md

File metadata and controls

链表

Problems

LeetCode 0002 两数相加 (中等, 2021-10)

LeetCode 0019 删除链表的倒数第N个结点 (中等, 2022-01)

LeetCode 0025 K个一组翻转链表 (困难, 2022-02)

LeetCode 0086 分隔链表 (中等, 2021-10)

LeetCode 0143 重排链表 (中等, 2022-01)

LeetCode 0876 链表的中间结点 (简单, 2022-01)

剑指Offer 0600 从尾到头打印链表 (简单, 2021-11)

剑指Offer 1800 删除链表的节点 (简单, 2021-11)

剑指Offer 2200 链表中倒数第k个节点 (简单, 2021-11)

剑指Offer 2400 反转链表 (简单, 2021-11)

剑指Offer 2500 合并两个排序的链表 (简单, 2021-11)

剑指Offer 3500 复杂链表的复制（深拷贝） (中等, 2021-12)

剑指Offer 5200 两个链表的第一个公共节点 (简单, 2022-01)

牛客 0002 重排链表 (中等, 2022-01)

牛客 0003 链表中环的入口结点 (简单, 2022-01)

牛客 0004 判断链表中是否有环 (简单, 2022-01)

牛客 0021 链表内指定区间反转 (中等, 2022-01)

牛客 0023 划分链表 (中等, 2022-01)

牛客 0024 删除有序链表中重复的元素-II (中等, 2022-01)

牛客 0025 删除有序链表中重复的元素-I (中等, 2022-01)

牛客 0033 合并两个排序的链表 (简单, 2022-02)

牛客 0040 链表相加(二) (中等, 2022-03)

牛客 0050 链表中的节点每k个一组翻转 (中等, 2022-03)

牛客 0066 两个链表的第一个公共结点 (简单, 2022-03)

牛客 0070 单链表的排序 (简单, 2022-03)

`LeetCode 0002 两数相加 (中等, 2021-10)`

`LeetCode 0019 删除链表的倒数第N个结点 (中等, 2022-01)`

`LeetCode 0025 K个一组翻转链表 (困难, 2022-02)`

`LeetCode 0086 分隔链表 (中等, 2021-10)`

`LeetCode 0143 重排链表 (中等, 2022-01)`

`LeetCode 0876 链表的中间结点 (简单, 2022-01)`

`剑指Offer 0600 从尾到头打印链表 (简单, 2021-11)`

`剑指Offer 1800 删除链表的节点 (简单, 2021-11)`

`剑指Offer 2200 链表中倒数第k个节点 (简单, 2021-11)`

`剑指Offer 2400 反转链表 (简单, 2021-11)`

`剑指Offer 2500 合并两个排序的链表 (简单, 2021-11)`

`剑指Offer 3500 复杂链表的复制（深拷贝） (中等, 2021-12)`

`剑指Offer 5200 两个链表的第一个公共节点 (简单, 2022-01)`

`牛客 0002 重排链表 (中等, 2022-01)`

`牛客 0003 链表中环的入口结点 (简单, 2022-01)`

`牛客 0004 判断链表中是否有环 (简单, 2022-01)`

`牛客 0021 链表内指定区间反转 (中等, 2022-01)`

`牛客 0023 划分链表 (中等, 2022-01)`

`牛客 0024 删除有序链表中重复的元素-II (中等, 2022-01)`

`牛客 0025 删除有序链表中重复的元素-I (中等, 2022-01)`

`牛客 0033 合并两个排序的链表 (简单, 2022-02)`

`牛客 0040 链表相加(二) (中等, 2022-03)`

`牛客 0050 链表中的节点每k个一组翻转 (中等, 2022-03)`

`牛客 0066 两个链表的第一个公共结点 (简单, 2022-03)`

`牛客 0070 单链表的排序 (简单, 2022-03)`