题目：

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

输入：[{1,2,3},{4,5,6,7}]
输出：{1,2,3,4,5,6,7}

解题思路：

先把 k 条链表二分再二分，直到每组只剩 0/1 条链表，然后自底向上两两合并，最终得到一条完整的有序链表。
1.拆半
把 k 条链表平均分成左右两半，递归处理。

2.递归基
如果区间里没有链表 → 返回 nil；
如果区间里只有一条链表 → 直接返回它（已经有序）。

3.合并
对左右两半的返回结果，执行标准的「合并两个有序链表」操作。

4.返回
把合并后的头节点往上层返回，最终得到总头节点。

输入：
lists = [ L1, L2, L3, L4 ]
L1: 1→4→5
L2: 1→3→4
L3: 2→6
L4: 0→8

1.拆半
                      merge[0,3]
                      /         \
               merge[0,1]      merge[2,3]
               /       \        /       \
          merge[0,0] merge[1,1] merge[2,2] merge[3,3]
             |         |         |         |
            L1        L2        L3        L4
                 到达叶子时直接返回链表本身。

2.合并（自底向上）
    2.1第一层合并
                L1  1→4→5     L2  1→3→4
                 \            /
                  \          /
                   mergeTwo →  1→1→3→4→4→5

                L3  2→6       L4  0→8
                 \            /
                  \          /
                   mergeTwo →  0→2→6→8

    2.2第二层合并
                1→1→3→4→4→5
                     \
                      \          0→2→6→8
                       \        /
                        mergeTwo → 0→1→1→2→3→4→4→5→6→8

3.最终返回

                0→1→1→2→3→4→4→5→6→8
                ↑
                head

4.系统流程

    分治方向  ↓                 合并方向  ↑
    +-------------------------------+
    | 4 条链表 → 2 条 → 1 条        |
    | 长度  k       k/2     1       |
    | 代价  O(Nlogk)                |
    +-------------------------------+

具体代码：

// 合并两个有序链表
// 输入：l1, l2 均为升序链表头节点
// 输出：合并后的升序链表头节点
func mergeTwo(l1, l2 *ListNode) *ListNode {
	// 哨兵节点，简化边界判断，避免处理空头问题
	dummy := &ListNode{}
	// cur 始终指向结果链表的最后一个节点
	cur := dummy

	// 同时遍历两个链表，直到其中一个被耗尽
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			// 将 l1 的头节点接到结果链表
			cur.Next = l1
			// l1 向后移动一位
			l1 = l1.Next
		} else {
			// 将 l2 的头节点接到结果链表
			cur.Next = l2
			// l2 向后移动一位
			l2 = l2.Next
		}
		// cur 前进到新加入的节点
		cur = cur.Next
	}

	// 至多还剩一个链表非空，直接接上去即可（已有序）
	if l1 != nil {
		cur.Next = l1
	}
	if l2 != nil {
		cur.Next = l2
	}

	// dummy.Next 即为合并后的头节点
	return dummy.Next
}

// 分治：合并 lists[l..r] 区间内的所有链表
// 输入：lists 链表切片，l、r 为闭区间左右端点
// 输出：合并后的有序链表头节点
func divide(lists []*ListNode, l, r int) *ListNode {
	// 非法区间，返回空
	if l > r {
		return nil
	}
	// 区间内只剩一个链表，直接返回
	if l == r {
		return lists[l]
	}

	// 取中点，将区间一分为二
	mid := (l + r) >> 1 // 等价于 (l+r)/2，但位运算更快
	// 递归合并左半部分
	left := divide(lists, l, mid)
	// 递归合并右半部分
	right := divide(lists, mid+1, r)

	// 将两个已合并好的有序链表再合并
	return mergeTwo(left, right)
}

// 合并 k 个升序链表（主入口）
// 输入：lists 是 k 条升序链表的头节点切片，可能为空
// 输出：一条升序链表的头节点；若输入为空则返回 nil
func mergeKLists(lists []*ListNode) *ListNode {
	// 特判：没有链表需要合并
	if len(lists) == 0 {
		return nil
	}

	// 对整个区间 [0, len(lists)-1] 进行分治合并
	return divide(lists, 0, len(lists)-1)
}

题目：

判断给定的链表中是否有环。如果有环则返回true，否则返回false。
输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时，对应的链表结构如下图所示

3 → 2 → 0 → -4
    ↑________|

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。

输入：{3,2,0,-4},1
返回值：true
说明：第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成      传入的head为一个带环的链表，返回true   

输入：{1},-1
输出：false
说明：第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false  

解题思路：

无环的链表最后节点指向nil,但如果这个链表很长和∏一样那很难判断。
所以换一种思考方式：快慢指针
假设有两个人在操场跑步，一个快(A)另一个慢(B)
无环链表是100冲刺
有环链表则是一直绕圈跑，知道A把B套圈了

具体代码：

func hasCycle( head *ListNode ) bool {
    // write code here
    //判断是否有成环的条件
    if head ==nil || head.Next == nil{
        return false
    }
    //快慢指针
    // 初始化快慢指针
    slow := head
    fast :=slow.Next
    //开始循环
    for fast != nil && fast.Next != nil{
         if slow == fast {
            // 如果快慢指针相遇，说明存在环
            return true
        }
        //快慢指针向后移
        slow = slow.Next
        fast = fast.Next.Next
    }
    return false
}

题目：

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

1 → 2 → 3
      ↗  ↘
     5 ←—— 4

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表。

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

输入：{1,2},{3,4,5}
输出：3
说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3  

输入：{1},{}
输出："null"
说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"   

输入：{},{2}
输出：2
说明：环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

解题思路：

观察题目可以发现这个链条是不重复的。
说以需要一个哈希表存储已经遍历的数据
如果当前节点已经在哈希表中，说明存在环，且这是环的入口节点
如果遍历到链表末尾（nil），说明不存在环

具体代码：

func EntryNodeOfLoop(pHead *ListNode) *ListNode {
	// 建立一个哈希表
	visited := make(map[*ListNode]bool)
	for pHead != nil {
		// 如果当前节点已经在哈希表中，说明存在环，且这是环的入口节点
		if visited[pHead] {
			return pHead
		}
		// 将当前节点加入哈希表
		visited[pHead] = true
		// 移动到下一个节点
		pHead = pHead.Next
	}
	// 如果遍历到链表末尾（nil），说明不存在环
	return nil
}

题目：

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
1 -> 2 -> 3 -> 4 -> 5
其中有蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

输入：{1,2,3,4,5},2
输出：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。

输入：{2},8
输出：{}

解题思路：

这道题很简单，我们只需要知道链表的长度
如果要返回的内容比链表长则返回nil

第一种：切片直接切(不推荐)

第二种：快慢指针
    假如输入:{1,2,3...},2
    快指针：先走到3
    然后快慢指针一起走，直到快指针.Next == nil
返回 快慢指针之间的链表

具体代码：

//切片
func FindKthToTail(pHead *ListNode, k int) *ListNode {
    if k <= 0 {
        return nil
    }
    // 顺序存入切片
    var nodes []*ListNode
    for cur := pHead; cur != nil; cur = cur.Next {
        nodes = append(nodes, cur)
    }
    n := len(nodes)
    if n < k { // 链表长度不足 k
        return nil
    }
    // 倒数第 k 个就是正数第 n-k 个（下标从 0 开始）
    return nodes[n-k]
}


//快慢指针
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
    // 初始化两个指针，fast 和 slow
    fast := pHead
    slow := pHead
    // 先让 fast 指针走 k 步
    for i := 0; i < k; i++ {
        if fast == nil { 
            // 如果链表长度小于 k，直接返回 nil
            return nil
        }
        fast = fast.Next
    }
    //然后fast和slow一起出发，fast为空则走到尽头
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    // 此时 slow 指向的就是倒数第 k 个节点
    return slow
}

题目：

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针

给出的链表为: 1→2→3→4→5,n=2.
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.

输入：{1,2},2 
返回值：{2} 

解题思路：

设哑结点 dummy := &ListNode{Next: head}，统一所有边界情况（如删头节点）。
让 fast、slow 都初始指向 dummy。
fast 先走 n+1 步，此时 fast 与 slow 之间相隔 n 个节点（slow 是待删节点的前驱）。
再同时移动 fast、slow，直到 fast == nil。
此时 slow.Next 就是要删的节点，执行
slow.Next = slow.Next.Next
返回 dummy.Next。

具体代码：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// write code here
	dummy := &ListNode{Next: head}
	fast, slow := dummy, dummy
	// fast 先走 n+1 步
	for i := 0; i <= n; i++ {
		fast = fast.Next
	}
	// 同时移动，直到 fast 到末尾
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	// 删除倒数第 n 个节点
	slow.Next = slow.Next.Next
	return dummy.Next
}

题目：

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
 

1 -> 2 -> 3
           ↘  
            6 -> 7
           ↗
     4 - >5

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

解题思路：

“让两个指针跑完自己的路再去跑对方的，第一次相遇的地方就是第一个公共节点；若没公共段，终点(null)相遇。”
背后只有三句话：
路程一样：a+c+b = b+c+a
速度一样：一次一步
所以第一次相等的位置一定是公共段起点（或同为 null）

具体代码：

func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    //判断特殊情况
    if pHead1 == nil || pHead2 == nil {
        return nil
    }
    //给两个链表一人一个指针
    // 初始化两个指针
    p1 := pHead1
    p2 := pHead2
     // 遍历两个链表
    for p1 != p2 {
        // 如果 p1 到达链表末尾，则切换到 pHead2
        if p1 == nil {
            p1 = pHead2
        } else {
            p1 = p1.Next
        }
        // 如果 p2 到达链表末尾，则切换到 pHead1
        if p2 == nil {
            p2 = pHead1
        } else {
            p2 = p2.Next
        }
    }
    // 返回第一个公共节点
    return p1
}

题目：

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

链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

        9 -> 3 -> 7
+            6 -> 3
-------------------
   1 -> 0 -> 0 -> 0

输入：[9,3,7],[6,3]
返回值：{1,0,0,0}

输入：[0],[6,3]
返回值：{6,3}

解题思路：

让个位先碰头
法① 反转两条链表；法② 把值压栈——目的都是把“个位”提到链表头。
同步扫描，逐位相加
sum = v1 + v2 + carry
carry = sum / 10
新建节点 sum % 10 头插到结果链（或尾插后再反转）。
处理最高位进位
循环结束 carry > 0 时再补一个节点 1。
按需恢复顺序
题目要高位在前 → 把结果链再反转一次；若允许个位在前 → 直接返回。
口诀：
“先倒序，再相加，有进位再补 1，最后看题决定反不反。”

具体代码：

// 主函数：以“高位在前”的链表形式返回两数之和
func addInList(head1, head2 *ListNode) *ListNode {
    /* 1. 先把两条链表反转，让个位跑到最前面，
          这样后续就可以从头开始逐位相加，如同手算加法 */
    head1 = reverseList(head1)
    head2 = reverseList(head2)

    /* 2. 创建哑结点 dummy，用来简化边界处理；
          current 始终指向结果链表的当前尾节点 */
    dummy := &ListNode{}
    current := dummy
    carry := 0 // 进位，初始为 0

    /* 3. 只要还有一个链表没走完，或者还有进位，就继续循环 */
    for head1 != nil || head2 != nil || carry > 0 {
        val1, val2 := 0, 0

        // 取当前节点的值（已反转，所以是个位、十位...）
        if head1 != nil {
            val1 = head1.Val
            head1 = head1.Next // 指针前移
        }
        if head2 != nil {
            val2 = head2.Val
            head2 = head2.Next
        }

        // 计算当前位总和，并拆分出“新数字”和“新进位”
        sum := val1 + val2 + carry
        carry = sum / 10                        // 更新进位
        current.Next = &ListNode{Val: sum % 10} // 新建节点接在结果链尾部
        current = current.Next                  // 移动尾指针
    }

    /* 4. 此时结果链表是“个位在前”的，再反转一次恢复成“高位在前” */
    result := reverseList(dummy.Next)
    return result
}

/* 反转链表：返回反转后的新头节点 */
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode = nil // 前驱节点，初始为 nil
    for head != nil {
        next := head.Next // 暂存后继
        head.Next = prev  // 当前节点指向前驱，完成反转
        prev = head       // prev 右移
        head = next       // head 右移
    }
    return prev // prev 成为新头
}

这些链表相关的知识已经能够解决开发过程中关于链表的算法

关于这些算法能在工作使用的场景

算法题	对应的真实开发场景	工程中的“变形”
合并 K 个升序链表	日志归并、多路外部排序、ElasticSearch 分段合并、Spark 小文件合并	节点里不一定存 int，可能是「文件句柄+偏移量」；归并函数要支持按时间戳/字典序自定义比较器
快慢指针判环	本地内存泄漏检测、Netty 对象池回收验证、RPC 调用链死循环兜底	节点里存的是弱引用，需要配合 GC 做可达性分析；快慢指针可改成“步长 2/3”提高检错速度
找环入口	微服务链路追踪里找“死循环重试”的起点、消息队列消费积压根因定位	把哈希表换成 IdentityHashMap，防止 equals 被覆写
倒数第 K 个节点	日志系统“ tail -n ”、DB 游标分页取“最新 N 条”、弹幕接口“滑动窗口”	一次可能取上千条，快慢指针要 batch 化，防止 cache miss
删除倒数第 N 个	发布系统“回滚最近 N 个版本”、配置中心“保留最近 N 个历史”	哑结点升级成“虚头 + 事务日志”，支持回滚
两个链表第一个公共节点	Git 找分叉点、微服务链路找“公共调用层”、前端虚拟 DOM diff 找相同父节点	把“长度差”优化成“哈希指纹对齐”，可并行加速
链表相加	大数计算（财务金额、加密参数）、低精度 ADC 采样累加、前端高精度计算器	节点存 0~9 太浪费，会改成 0~1e9 每段 9 位，减少 malloc 次数；再升级成 64 段 SIMD 并行加