LeetCode 1669 Merge In Between Linked Lists数组转换、双指针与递归三种解法及多语言实现深度解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 LeetCode 1669「合并两个链表Merge In Between Linked Lists」为核心系统讲解在单链表中删除区间[a, b]节点并原位插入另一条链表的三种经典思路——转数组Convert to Array、双指针Two Pointers与递归Recursion。本文不仅完整继承 articles/merge-in-between-linked-lists.md 中三种解法的直觉、算法步骤、8 种语言代码与复杂度分析还结合本仓库实际提交的 Python、Go、Java、Kotlin 源码进行佐证。读完本文你将掌握单链表指针重连的通用技巧、时空复杂度权衡方法以及如何避开插入点 off-by-one 等高频坑点。问题背景与题意理解mergeInBetween(list1, a, b, list2)要求给定链表list1与list2以及两个索引a、b满足1 a b list1.length - 1从list1中移除下标从a到b的节点然后将list2整体插入到被移除区间的位置最后返回list1的头节点。该题考察的核心是链表的**指针重连pointer rewiring**能力单向链表无法像数组那样按下标随机访问一切增删改都必须借助next指针的定向修改完成。题目本质上是两个操作的组合切断把list1中a-1号节点区间前一个节点的next指向list2的头续接把list2的尾节点next指向list1中b1号节点区间后一个节点。之所以是a - 1和b 1是因为题目索引是0-baseda、b是list1中的下标被删除区间是闭区间[a, b]因此衔接点必须落在区间外的相邻节点上。这一区间闭开边界的理解直接决定了后续所有解法的正确性也是本仓库 articles/merge-in-between-linked-lists.md 开篇强调先掌握以下前置知识的原因。前置知识Prerequisites在动手实现前需要具备以下基础这也是本文关联文档明确列出的要求链表Linked Lists理解单链表节点结构与遍历方式——每个节点包含val与指向下一个节点的next指针遍历靠不断前进cur cur.next指针操纵Pointer Manipulation通过修改next指针来重连节点连接关系这是链表题的立身之本双指针Two Pointers同时在链表中追踪多个位置常用一个计数器配合指针完成走到第 N 个节点的定位任务。解法一转数组Convert To Array——以空间换直接访问核心直觉Intuition题目需要删除list1中下标a到b的节点并插入list2而链表的短板恰恰是无法按下标 O(1) 访问节点。既然这样索性把list1的所有节点存入一个数组从而获得任意下标的直接访问能力连接a-1号节点 →list2头节点再连接list2尾节点 →b1号节点两步即可完成拼接。整个思路直白、不易出错非常适合面试时先讲清楚再做优化。算法步骤Algorithm遍历list1将所有节点依次存入一个数组arr将数组中下标为a - 1的节点的next指向list2的头节点遍历list2找到其最后一个节点尾节点将list2尾节点的next指向数组中下标为b 1的节点返回list1的头节点。注意因为只是重新连线被删除区间[a, b]中的节点并不需要显式释放——它们只是从主链上脱钩后续自然无法从list1头节点出发被访问到在没有 GC 的语言中若需要内存管理则要单独处理见下文常见陷阱。多语言实现Python# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) - ListNode: cur list1 arr [] while cur: arr.append(cur) cur cur.next arr[a - 1].next list2 cur list2 while cur.next: cur cur.next cur.next arr[b 1] return list1Java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ public class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode cur list1; ListListNode arr new ArrayList(); while (cur ! null) { arr.add(cur); cur cur.next; } arr.get(a - 1).next list2; cur list2; while (cur.next ! null) { cur cur.next; } cur.next arr.get(b 1); return list1; } }C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) { ListNode* cur list1; vectorListNode* arr; while (cur) { arr.push_back(cur); cur cur-next; } arr[a - 1]-next list2; cur list2; while (cur-next) { cur cur-next; } cur-next arr[b 1]; return list1; } };JavaScript/** * Definition for singly-linked list. * class ListNode { * constructor(val 0, next null) { * this.val val; * this.next next; * } * } */ class Solution { /** * param {ListNode} list1 * param {number} a * param {number} b * param {ListNode} list2 * return {ListNode} */ mergeInBetween(list1, a, b, list2) { let cur list1; let arr []; while (cur) { arr.push(cur); cur cur.next; } arr[a - 1].next list2; cur list2; while (cur.next) { cur cur.next; } cur.next arr[b 1]; return list1; } }Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode { cur : list1 arr : []*ListNode{} for cur ! nil { arr append(arr, cur) cur cur.Next } arr[a-1].Next list2 cur list2 for cur.Next ! nil { cur cur.Next } cur.Next arr[b1] return list1 }Kotlin/** * Example: * var li ListNode(5) * var v li.val * Definition for singly-linked list. * class ListNode(var val: Int) { * var next: ListNode? null * } */ class Solution { fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?): ListNode? { var cur list1 val arr mutableListOfListNode() while (cur ! null) { arr.add(cur) cur cur.next } arr[a - 1].next list2 cur list2 while (cur?.next ! null) { cur cur.next } cur?.next arr[b 1] return list1 } }Swift/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val 0; self.next nil; } * public init(_ val: Int) { self.val val; self.next nil; } * public init(_ val: Int, _ next: ListNode?) { self.val val; self.next next; } * } */ class Solution { func mergeInBetween(_ list1: ListNode?, _ a: Int, _ b: Int, _ list2: ListNode?) - ListNode? { var cur list1 var arr [ListNode]() while cur ! nil { arr.append(cur!) cur cur?.next } arr[a - 1].next list2 cur list2 while cur?.next ! nil { cur cur?.next } cur?.next arr[b 1] return list1 } }Rust// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: OptionBoxListNode, // } impl Solution { pub fn merge_in_between( list1: OptionBoxListNode, a: i32, b: i32, list2: OptionBoxListNode, ) - OptionBoxListNode { let mut arr: Veci32 Vec::new(); let mut cur list1; while let Some(node) cur { arr.push(node.val); cur node.next; } let mut vals2: Veci32 Vec::new(); let mut cur2 list2; while let Some(node) cur2 { vals2.push(node.val); cur2 node.next; } let mut result_vals: Veci32 Vec::new(); result_vals.extend_from_slice(arr[..a as usize]); result_vals.extend_from_slice(vals2); result_vals.extend_from_slice(arr[(b 1) as usize..]); let mut head None; for val in result_vals.iter().rev() { let mut node ListNode::new(val); node.next head; head Some(Box::new(node)); } head } }说明Rust 由于所有权机制无法像其他语言那样直接持有节点引用数组因此该版本退化为收集 val → 重组新链表的思路结果一致但语义上更接近值拷贝可作为 Rust 所有权约束下的参考实现。时间与空间复杂度时间复杂度$O(n m)$——遍历list1一次、遍历list2一次空间复杂度$O(n)$——数组额外存储了list1的全部n个节点。其中 $n$ 为list1的长度$m$ 为list2的长度。解法二双指针Two Pointers——O(1) 额外空间的原地拼接核心直觉Intuition转数组法虽然直观但多花了 $O(n)$ 的空间。实际上我们根本不需要保存所有节点——只需要记住两个关键位置即可区间前的节点a - 1号与区间后的节点b 1号。用一个指针配合计数器在list1上走两段路先走到a - 1号节点记下它再继续走到b 1号节点最后把这两端分别与list2的头尾接上。这就是本文关联文档推荐的首选解法也是本仓库 Python、Go、Java、Kotlin 四个已提交实现共同采用的标准写法。算法步骤Algorithm在list1头部初始化指针curr计数器i置为0将curr向前移动直到i等于a - 1把当前节点记为head即区间前节点继续向前移动curr直到i超过b此时curr指向被移除区段之后的第一个节点即b 1号节点令head.next指向list2的头节点遍历list2找到其尾节点令list2尾节点的next指向curr返回list1的头节点。一个值得注意的细节是两个循环共用同一个计数器i第二个循环从i a - 1的现场继续累加到i b因此总共只遍历了 $O(n)$ 个节点无需二次扫描。多语言实现Python# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) - ListNode: curr list1 i 0 while i a - 1: curr curr.next i 1 head curr while i b: curr curr.next i 1 head.next list2 while list2.next: list2 list2.next list2.next curr return list1Java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ public class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { ListNode curr list1; int i 0; while (i a - 1) { curr curr.next; i; } ListNode head curr; while (i b) { curr curr.next; i; } head.next list2; while (list2.next ! null) { list2 list2.next; } list2.next curr; return list1; } }C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) { ListNode* curr list1; int i 0; while (i a - 1) { curr curr-next; i; } ListNode* head curr; while (i b) { curr curr-next; i; } head-next list2; while (list2-next) { list2 list2-next; } list2-next curr; return list1; } };JavaScript/** * Definition for singly-linked list. * class ListNode { * constructor(val 0, next null) { * this.val val; * this.next next; * } * } */ class Solution { /** * param {ListNode} list1 * param {number} a * param {number} b * param {ListNode} list2 * return {ListNode} */ mergeInBetween(list1, a, b, list2) { let curr list1, i 0; while (i a - 1) { curr curr.next; i; } let head curr; while (i b) { curr curr.next; i; } head.next list2; while (list2.next) { list2 list2.next; } list2.next curr; return list1; } }Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode { curr : list1 i : 0 for i a-1 { curr curr.Next i } head : curr for i b { curr curr.Next i } head.Next list2 for list2.Next ! nil { list2 list2.Next } list2.Next curr return list1 }Kotlin/** * Example: * var li ListNode(5) * var v li.val * Definition for singly-linked list. * class ListNode(var val: Int) { * var next: ListNode? null * } */ class Solution { fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?): ListNode? { var curr list1 var i 0 while (i a - 1) { curr curr?.next i } val head curr while (i b) { curr curr?.next i } head?.next list2 var tail list2 while (tail?.next ! null) { tail tail.next } tail?.next curr return list1 } }Swift/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val 0; self.next nil; } * public init(_ val: Int) { self.val val; self.next nil; } * public init(_ val: Int, _ next: ListNode?) { self.val val; self.next next; } * } */ class Solution { func mergeInBetween(_ list1: ListNode?, _ a: Int, _ b: Int, _ list2: ListNode?) - ListNode? { var curr list1 var i 0 while i a - 1 { curr curr?.next i 1 } let head curr while i b { curr curr?.next i 1 } head?.next list2 var tail list2 while tail?.next ! nil { tail tail?.next } tail?.next curr return list1 } }Rustimpl Solution { pub fn merge_in_between( list1: OptionBoxListNode, a: i32, b: i32, list2: OptionBoxListNode, ) - OptionBoxListNode { let mut dummy Some(Box::new(ListNode { val: 0, next: list1 })); let mut cur mut dummy; for _ in 0..a { cur mut cur.as_mut().unwrap().next; } let mut tail cur.as_mut().unwrap().next.take(); for _ in 0..(b - a) { tail tail.unwrap().next; } cur.as_mut().unwrap().next list2; let mut cur cur; while cur.as_ref().unwrap().next.is_some() { cur mut cur.as_mut().unwrap().next; } cur.as_mut().unwrap().next tail; dummy.unwrap().next } }说明Rust 版本借助哑节点dummy node规避头节点特判并通过take()从链上摘下待删除区段再续接list2既体现了双指针思路也展示了在OptionBoxListNode所有权模型下安全改写链表的惯用法。时间与空间复杂度时间复杂度$O(n m)$——list1只完整走过一遍list2额外遍历一遍找尾空间复杂度$O(1)$ 额外空间——只使用了常数个指针变量。其中 $n$ 为list1的长度$m$ 为list2的长度。仓库源码佐证本仓库中已提交的四个语言实现与上文双指针解法完全一致可作为可直接运行的正确性参照python/1669-merge-in-between-linked-lists.pywhile i a - 1定位headwhile i b越过删除区段随后head.next list2并遍历list2找到尾节点完成续接go/1669-merge-in-between-linked-lists.go逻辑与 Python 版一一对应仅将curr.next替换为curr.NextGo 导出字段命名java/1669-merge-in-between-linked-lists.java循环条件list2.next ! null显式判空其余结构与上述实现一致kotlin/1669-merge-in-between-linked-lists.kt在可空类型ListNode?上使用?.next安全调用并单独引入tail变量遍历list2尾部。可见该仓库将双指针法作为该题的标准解答收录这也印证了它是三种解法中综合最优的选择。解法三递归Recursion——用调用栈代替显式计数器核心直觉Intuition递归解法把指针移动抽象为缩小问题规模每深入一层list1就把a和b各减 1直到某个基准条件成立。当a减到 1 时当前节点正是插入点即a-1号节点此时把list2挂上去随后携带list2的尾节点继续递归让b继续倒数当b减到 0 时说明待删除节点已全部越过把list2的尾部接到剩余链表上即可。递归深度的上限就是list1的长度因此空间复杂度为 $O(n)$。算法步骤Algorithm若a 1说明到达插入点保存list1.next为nxt令list1.next list2遍历到list2末尾找到尾节点以nxt、a 0、b - 1、list2的尾节点为参数递归调用自身返回list1。若b 0说明所有待删除节点均已跳过令list2.next list1.next把list2尾部接到list1剩余部分上返回list1。其他情况对list1.next以a - 1、b - 1递归调用返回list1。整个递归过程以递减的a定位插入点、以递减的b控制跳过的节点数两套计数在同一个调用链上协同工作是把迭代式指针移动改写为函数式状态传递的典型示范。多语言实现Python# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) - ListNode: if a 1 : nxt list1.next list1.next list2 while list2.next: list2 list2.next self.mergeInBetween(nxt, 0, b - 1, list2) return list1 if b 0: list2.next list1.next return list1 self.mergeInBetween(list1.next, a - 1, b - 1, list2) return list1Java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ public class Solution { public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) { if (a 1) { ListNode nxt list1.next; list1.next list2; while (list2.next ! null) { list2 list2.next; } mergeInBetween(nxt, 0, b - 1, list2); return list1; } if (b 0) { list2.next list1.next; return list1; } mergeInBetween(list1.next, a - 1, b - 1, list2); return list1; } }C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) { if (a 1) { ListNode* nxt list1-next; list1-next list2; while (list2-next) { list2 list2-next; } mergeInBetween(nxt, 0, b - 1, list2); return list1; } if (b 0) { list2-next list1-next; return list1; } mergeInBetween(list1-next, a - 1, b - 1, list2); return list1; } };JavaScript/** * Definition for singly-linked list. * class ListNode { * constructor(val 0, next null) { * this.val val; * this.next next; * } * } */ class Solution { /** * param {ListNode} list1 * param {number} a * param {number} b * param {ListNode} list2 * return {ListNode} */ mergeInBetween(list1, a, b, list2) { if (a 1) { let nxt list1.next; list1.next list2; while (list2.next) { list2 list2.next; } this.mergeInBetween(nxt, 0, b - 1, list2); return list1; } if (b 0) { list2.next list1.next; return list1; } this.mergeInBetween(list1.next, a - 1, b - 1, list2); return list1; } }Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func mergeInBetween(list1 *ListNode, a int, b int, list2 *ListNode) *ListNode { if a 1 { nxt : list1.Next list1.Next list2 for list2.Next ! nil { list2 list2.Next } mergeInBetween(nxt, 0, b-1, list2) return list1 } if b 0 { list2.Next list1.Next return list1 } mergeInBetween(list1.Next, a-1, b-1, list2) return list1 }Kotlin/** * Example: * var li ListNode(5) * var v li.val * Definition for singly-linked list. * class ListNode(var val: Int) { * var next: ListNode? null * } */ class Solution { fun mergeInBetween(list1: ListNode?, a: Int, b: Int, list2: ListNode?): ListNode? { if (a 1) { val nxt list1?.next list1?.next list2 var tail list2 while (tail?.next ! null) { tail tail.next } mergeInBetween(nxt, 0, b - 1, tail) return list1 } if (b 0) { list2?.next list1?.next return list1 } mergeInBetween(list1?.next, a - 1, b - 1, list2) return list1 } }Swift/** * Definition for singly-linked list. * public class ListNode { * public var val: Int * public var next: ListNode? * public init() { self.val 0; self.next nil; } * public init(_ val: Int) { self.val val; self.next nil; } * public init(_ val: Int, _ next: ListNode?) { self.val val; self.next next; } * } */ class Solution { func mergeInBetween(_ list1: ListNode?, _ a: Int, _ b: Int, _ list2: ListNode?) - ListNode? { if a 1 { let nxt list1?.next list1?.next list2 var tail list2 while tail?.next ! nil { tail tail?.next } _ mergeInBetween(nxt, 0, b - 1, tail) return list1 } if b 0 { list2?.next list1?.next return list1 } _ mergeInBetween(list1?.next, a - 1, b - 1, list2) return list1 } }Rustimpl Solution { pub fn merge_in_between( list1: OptionBoxListNode, a: i32, b: i32, list2: OptionBoxListNode, ) - OptionBoxListNode { fn helper( list1: OptionBoxListNode, a: i32, b: i32, list2: OptionBoxListNode, ) - OptionBoxListNode { let mut node list1.unwrap(); if a 1 { let nxt node.next.take(); let mut tail list2; let mut result_vals vec![node.val]; let mut cur tail; let mut l2_vals Vec::new(); while let Some(n) cur { l2_vals.push(n.val); cur n.next; } let mut remaining nxt; for _ in 0..b { remaining remaining.unwrap().next; } let mut vals result_vals; vals.extend(l2_vals); let mut cur remaining; while let Some(n) cur { vals.push(n.val); cur n.next; } let mut head None; for val in vals.iter().rev() { let mut n ListNode::new(val); n.next head; head Some(Box::new(n)); } return head; } node.next helper(node.next, a - 1, b - 1, list2); Some(node) } helper(list1, a, b, list2) } }时间与空间复杂度时间复杂度$O(n m)$——每个节点至多被访问常数次空间复杂度$O(n)$——递归调用栈深度最多为 $n$。其中 $n$ 为list1的长度$m$ 为list2的长度。需要提醒的是递归解法在超长链表上可能触发调用栈溢出实际工程中优先考虑迭代写法它更适合作为面试中展示把循环改写为递归思维能力的加分项。三种解法横向对比解法核心思想时间复杂度空间复杂度适用场景转数组Convert to Array用数组换取按下标直接访问$O(n m)$$O(n)$思路最直观、最不易写错适合先讲清楚解法双指针Two Pointers只记录a-1与b1两个关键节点$O(n m)$$O(1)$综合最优面试与工程首选本仓库标准实现递归Recursion用调用栈代替计数器递减a、b定位$O(n m)$$O(n)$递归栈展示递归思维链表极长时需警惕栈溢出三种解法的时间复杂度相同差异集中在空间开销与可读性上转数组法最直观但空间最差双指针法兼顾简洁与高效递归法提供了一种函数式视角但受限于栈深度。常见陷阱Common Pitfalls插入点的 off-by-one 错误a - 1号节点应指向list2list2的尾节点应指向b 1号节点。如果直接使用下标a或b进行连接拼接结果会错位——要么多删一个节点要么少删一个节点。这是本类题目出现频率最高的错误务必牢记区间[a, b]是闭区间。忘记寻找 list2 的尾节点将a - 1号节点连到list2头节点之后必须遍历list2找到尾节点再把尾节点连到list1的剩余部分。如果跳过这一步合并后的链表会在list2的末尾断掉导致结果不完整——这在三份解法包括仓库标准实现中都是单独的显式遍历步骤可见其不可省略。未处理被删除的节点下标a到b之间的节点已不再属于结果链表。在没有垃圾回收的语言如 C/C中若这些节点是动态分配的需要单独释放以避免内存泄漏在带 GC 的语言如 Python、Java、Go、Kotlin中这些节点失去引用后会自动被回收无需额外处理。此外若被摘除的区段后续还有引用需求也可考虑将其单独保存复用。总结LeetCode 1669 是检验链表基本功的经典题目它要求你在理解 0-based 闭区间语义的前提下完成定位 → 切断 → 插入 → 续接四个动作。三种解法层层递进——转数组法以空间换直观、双指针法以 O(1) 空间达到最优、递归法以函数式视角换一种实现思路。若要在面试与实战中给出最稳妥的答案建议掌握并优先采用双指针解法同时理解转数组与递归两种变体的取舍完整的多语言实现与讲解可随时回溯 articles/merge-in-between-linked-lists.md仓库中 python/1669-merge-in-between-linked-lists.py、go/1669-merge-in-between-linked-lists.go、java/1669-merge-in-between-linked-lists.java、kotlin/1669-merge-in-between-linked-lists.kt 则是经过验证的可运行参考实现。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考