C++程序平铺链表

简介

平铺链表（Flatten Linked List）是将嵌套的链表铺平成一个线性的链表的操作。形象地说，就是将一个多层级的链表变成只有一层级的链表。

例如，下面这个嵌套的链表：

1 -> 2 -> 3 -> 4 -> 5
         |         |
         6 -> 7    8 -> 9 -> 10
         |              |
         11             12 -> 13
                          |
                          14 -> 15 -> NULL

将变成如下的线性链表：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> NULL

本文将介绍如何通过C++程序来实现平铺链表的操作。

实现过程

定义数据结构

首先，我们需要定义链表节点的数据结构。由于链表是嵌套的，我们需要为链表节点增加一个子链表的指针。

struct ListNode {
    int val;
    ListNode *next;
    ListNode *child;
};

其中，val 表示节点的值；next 指向下一个相邻的节点；child 指向子链表的头节点。

递归实现

平铺链表可以通过递归实现。我们可以先将子链表铺平，然后将当前链表的尾节点与子链表的头节点相连。

class Solution {
public:
    ListNode* flatten(ListNode* head) {
        if (!head) {
            return nullptr;
        }

        ListNode *tail = head;
        while (tail->next) {
            tail = tail->next;
        }

        ListNode *cur = head;
        while (cur) {
            if (cur->child) {
                ListNode *next = cur->next;
                ListNode *child_tail = flatten(cur->child);
                cur->next = cur->child;
                cur->next->prev = cur;
                cur->child = nullptr;
                child_tail->next = next;
                if (next) {
                    next->prev = child_tail;
                }
                cur = tail;
            } else {
                cur = cur->next;
            }
        }

        return head;
    }
};

代码中涉及到一些指针的操作，下面将分别介绍它们的含义。

tail：定义一个指针，表示当前链表的尾节点。
next：记录当前节点的下一个相邻节点。
child_tail：定义一个指针，表示子链表的尾节点。

迭代实现

除了递归实现外，我们还可以通过迭代实现平铺链表。

class Solution {
public:
    ListNode* flatten(ListNode* head) {
        if (!head) {
            return nullptr;
        }

        ListNode *prev = nullptr;
        stack<ListNode *> stk;
        stk.push(head);

        while (!stk.empty()) {
            ListNode *cur = stk.top();
            stk.pop();

            if (prev) {
                prev->next = cur;
                cur->prev = prev;
            }
            prev = cur;

            if (cur->next) {
                stk.push(cur->next);
            }
            if (cur->child) {
                stk.push(cur->child);
                cur->child = nullptr;
            }
        }

        return head;
    }
};

代码中使用了一个栈，记录下一个要访问的节点。当栈为空时，说明所有节点已经访问完，即平铺链表完成。

示例代码

下面是一个完整的示例代码。

#include <iostream>
#include <stack>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode *child;
};

class Solution {
public:
    ListNode* flatten(ListNode* head) {
        if (!head) {
            return nullptr;
        }

        ListNode *prev = nullptr;
        stack<ListNode *> stk;
        stk.push(head);

        while (!stk.empty()) {
            ListNode *cur = stk.top();
            stk.pop();

            if (prev) {
                prev->next = cur;
                cur->prev = prev;
            }
            prev = cur;

            if (cur->next) {
                stk.push(cur->next);
            }
            if (cur->child) {
                stk.push(cur->child);
                cur->child = nullptr;
            }
        }

        return head;
    }
};

void printList(ListNode *head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    ListNode *head = new ListNode{1, nullptr, nullptr};
    head->next = new ListNode{2, nullptr, nullptr};
    head->next->next = new ListNode{3, nullptr, nullptr};
    head->next->next->next = new ListNode{4, nullptr, nullptr};
    head->next->next->next->next = new ListNode{5, nullptr, nullptr};
    head->next->child = new ListNode{6, nullptr, nullptr};
    head->next->child->next = new ListNode{7, nullptr, nullptr};
    head->next->next->next->child = new ListNode{8, nullptr, nullptr};
    head->next->next->next->child->next = new ListNode{9, nullptr, nullptr};
    head->next->next->next->child->next->next = new ListNode{10, nullptr, nullptr};
    head->next->child->child = new ListNode{11, nullptr, nullptr};
    head->next->next->next->child->next->child = new ListNode{12, nullptr, nullptr};
    head->next->next->next->child->next->child->next = new ListNode{13, nullptr, nullptr};
    head->next->next->next->child->next->child->next->child = new ListNode{14, nullptr, nullptr};
    head->next->next->next->child->next->child->next->child->next = new ListNode{15, nullptr, nullptr};

    Solution s;
    head = s.flatten(head);
    printList(head);

    return 0;
}