Microsoft VO 面试真题解析：Merge In Between 链表拼接

Merge In Between

Description

Consider two linked lists, list1 and list2, and two integers, i and j. Replace the nodes from the ith to the jth position in list1 with all the nodes from list2.

• The portion of list1 from the 1st to (i-1)th nodes remains unchanged.
• All nodes of list2 are inserted after the (i-1)th node.
• The portion of list1 starting from the (j+1)th node is appended after list2.

Example

i = 2
j = 3
list1 = 1 -> 2 -> 3 -> 4 -> 5
list2 = 6 -> 7 -> 8 -> 9

这道题考察单链表的节点重连。核心思路是先找到 list1 中第 i-1 个节点和第 j+1 个节点，再把 list2 整段插入到中间，最后将 list2 的尾节点连接回后半段即可。整个过程只需要一次线性遍历，重点是正确维护前驱、后继和尾节点指针，避免断链或重复连接。