C++程序 平铺链表

C++程序 平铺链表

给定一个链表,其中每个节点都代表一个链表,并包含其类型的两个指针:

  1. 链表中下一个节点的指针(下面的代码中称为‘right’指针)。
  2. 指向这个节点所指向的链表的指针(下面的代码中称为‘down’指针)。

所有的链表都是已排序的。请看下面的例子

       5 -> 10 -> 19 -> 28
       |    |     |     |
       V    V     V     V
       7    20    22    35
       |          |     |
       V          V     V
       8          50    40
       |                |
       V                V
       30               45

编写一个函数flatten()将这些链表压成一个单链表。被压缩的链表也应该是已排序的。例如,针对上面的输入列表,输出列表应该是5->7->8->10->19->20->22->28->30->35->40->45->50。

思路是使用链表归并排序的merge()过程。我们使用merge()一次次地将列表合并。我们递归地将当前列表与已经压平的列表merge()。

down指针用于连接被压缩的链表的节点。

下面是以上方法的实施:

// C++ program for flattening a
// Linked List
#include <bits/stdc++.h>
using namespace std;
 
// Link list node
class Node
{
    public:
    int data;
    Node *right, *down;
};
 
Node* head = NULL;
 
// An utility function to merge
// two sorted linked lists
Node* merge(Node* a, Node* b)
{   
    // If first linked list is empty
    // then second is the answer
    if (a == NULL)
        return b;
 
    // If second linked list is empty
    // then first is the result
    if (b == NULL)
        return a;
 
    // Compare the data members of the
    // two linked lists and put the larger
    // one in the result
    Node* result;
 
    if (a->data < b->data)
    {
        result = a;
        result->down = merge(a->down, b);
    }
 
    else
    {
        result = b;
        result->down = merge(a, b->down);
    }
    result->right = NULL;
    return result;
}
 
Node* flatten(Node* root)
{   
    // Base Cases
    if (root == NULL ||
        root->right == NULL)
        return root;
 
    // Recur for list on right
    root->right = flatten(root->right);
 
    // Now merge
    root = merge(root, root->right);
 
    // Return the root
    // It will be in turn merged
    // with its left
    return root;
}
 
// Utility function to insert a node at
// beginning of the linked list
Node* push(Node* head_ref, int data)
{   
    // Allocate the Node &
    // Put in the data
    Node* new_node = new Node();
 
    new_node->data = data;
    new_node->right = NULL;
 
    // Make next of new Node as head
    new_node->down = head_ref;
 
    // Move the head to point to
    // new Node
    head_ref = new_node;
 
    return head_ref;
}
 
void printList()
{
    Node* temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->down;
    }
    cout << endl;
}
 
// Driver code
int main()
{   
    /* Create the following linked list
        5 -> 10 -> 19 -> 28
        |    |     |     |
        V    V     V     V
        7    20    22    35
        |          |     |
        V          V     V
        8          50    40
        |                |
        V                V
        30               45
    */
    head = push(head, 30);
    head = push(head, 8);
    head = push(head, 7);
    head = push(head, 5);
 
    head->right = push(head->right, 20);
    head->right = push(head->right, 10);
 
    head->right->right =
    push(head->right->right, 50);
    head->right->right =
    push(head->right->right, 22);
    head->right->right =
    push(head->right->right, 19);
 
    head->right->right->right =
    push(head->right->right->right, 45);
    head->right->right->right =
    push(head->right->right->right, 40);
        head->right->right->right =
    push(head->right->right->right, 35);
    head->right->right->right =
    push(head->right->right->right, 20);
 
    // Flatten the list
    head = flatten(head);
 
    printList();
    return 0;
}
// This code is contributed by rajsanghavi9.```  

输出:

5 7 8 10 19 20 20 22 30 35 40 45 50

时间复杂度: O(NNM)-其中N为主链表中的节点数(可用右指针访问),M为单个子链表中的节点数(可用下指针访问)。

空间复杂度: O(N*M),因为递归函数将使用等于列表中所有元素的递归堆栈的大小。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例