编写扁平化有序多层链表代码遇阻，仅能处理首个子链表

问题背景 #

给定包含n个节点的多层链表，每个节点包含两个指针：

• next：指向链表的下一个节点
• child：指向以当前节点为头的有序子链表
  任务要求将该多层链表扁平化为单层有序链表。

问题现状 #

当前实现仅能完成首个子链表的扁平化，程序后续会异常退出。

当前代码 #

public class Solution {
    public static Node flattenLinkedList(Node head) {
        //Write your code here
        if(head == null||head.next==null){
            return head;
        }
        Node childptr = head.child;
        Node listptr = head;
        Node temp = listptr.next;
        while(temp!=null){
            // Node next = childptr.child;
            childptr.next = listptr.next;
            listptr.next = childptr;
            listptr = listptr.next;
            
            childptr = childptr.child;
            if(childptr==null){
                childptr = temp.child;
                listptr = temp;
                temp = temp.next;
            }
        }
        return head;
    }
}

问题分析 #

原代码存在多个逻辑漏洞：

1. 空指针风险：如果头节点的child为null，childptr.next = listptr.next会直接抛出空指针异常
2. 子链表处理不彻底：仅处理了当前节点的直接child，没有递归处理child的子链表
3. 链表拼接逻辑错误：修改next指针时没有正确维护链表的连续性，导致后续节点丢失或循环引用

修正方案（递归实现） #

采用递归思路，逐个处理每个节点的child链表，将其拼接到当前节点与next节点之间，同时递归扁平化child链表：

public class Solution {
    public static Node flattenLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        
        Node current = head;
        // 遍历主链表的每个节点
        while (current != null) {
            // 如果当前节点有子链表
            if (current.child != null) {
                // 先递归扁平化子链表
                Node flattenedChild = flattenLinkedList(current.child);
                // 保存当前节点的下一个节点
                Node nextNode = current.next;
                // 将当前节点指向扁平化后的子链表头
                current.next = flattenedChild;
                // 找到子链表的尾节点
                Node childTail = flattenedChild;
                while (childTail.next != null) {
                    childTail = childTail.next;
                }
                // 将子链表尾节点指向原next节点
                childTail.next = nextNode;
                // 清空当前节点的child指针，避免重复处理
                current.child = null;
                // 跳转到原next节点继续处理
                current = nextNode;
            } else {
                // 没有子链表则直接移动到下一个节点
                current = current.next;
            }
        }
        return head;
    }
}

方案说明 #

1. 递归扁平化子链表：确保每个子链表的多层结构都被扁平化为单层
2. 链表拼接逻辑：将扁平化后的子链表插入到当前节点和原next节点之间，维护链表的连续性
3. 清空child指针：避免后续遍历重复处理同一子链表
4. 空值处理：对head为null的情况直接返回，避免空指针异常

内容的提问来源于stack exchange，提问作者Great412