функция, чтобы сгладить список в один список

Question

Учитывая структуру связанного списка, где каждый узел представляет связанный список и содержит два указателя своего типа:

(i) указатель на следующий узел в основном списке.
(ii) указатель на связанный список, где этот узел является головным.

Напишите функцию C, чтобы свести список в один связанный список.

Например.

Если данный связанный список

  1 -- 5 -- 7 -- 10 
  |    |    | 
  2    6    8 
  |    | 
  3    9 
  | 
  4 

затем преобразовать его в

1 - 2 - 3 - 4 - 5 - 6 - 9 - 7 - 8 -10 

Мое решение

struct node {
    int data; 
    struct node *fwd; //pointer to next node in the main list. 
    struct node *down; //pointer to a linked list where this node is head. 
}*head,*temp,*temp2; 

temp=head; 
while(temp->fwd!=NULL) {
    temp2=temp->fwd; 
    while(temp->down!=NULL) {
        temp=temp->down;
    } 
    temp->down=temp2;
    temp->fwd=NULL;
    temp=temp2;
 }  

Пожалуйста, сообщите мне, если что-нибудь ... приветствуются другие решения и оптимизации

Answer 1

struct node* flatten_dfwalk(struct node * root)
{   

    struct node *lnode, *rnode, *temp;

    if (NULL == root)
    {
        return NULL;
    }


    lnode = flatten_dfwalk(root->down);
    rnode = flatten_dfwalk(root->next);

    if (NULL == lnode)
    {
        return root;
    }

    temp = lnode;
    while(lnode->next != NULL)
    {
        lnode = lnode->next;
    }

    lnode->next = root->next;
    root->next = temp;

    return root;
}

Answer 2

Если вы рассматриваете ссылку «вниз» как левый дочерний указатель, а ссылку «вперёд» как правый дочерний указатель, то вы ищите обход в порядке простого двоичного дерева. То есть вы посещаете узел; затем вы посещаете левых (вниз) детей, затем вы посещаете правых (вперед) детей. Это очень легко записать как рекурсивную функцию.

Ваше решение не будет проходить через любое дерево, если у первого узла будет только указатель вниз и указатель не вперед. Также он не будет искать вниз от последнего указателя, если он имеет указатели вниз (потому что у него нет прямого указателя).

Я думаю (но я не уверен - я не проверял это), что ваше решение сталкивается с проблемами на более густых деревьях, чем в примере. Если бы у узла 2 были прямые указатели, я думаю, что были бы проблемы с поиском этого поддерева.

Использовать рекурсию; это тривиально и надежно. Хотя вы можете исключить простую хвостовую рекурсию, для этого требуется нечто большее, чем простая хвостовая рекурсия.

Answer 3

Во-первых, важно, чтобы это заработало. Из-за while(temp->fwd!=NULL) ваше решение не работает для следующих сценариев:

A) 1 -- 2     B) 1 -- 3
        |        |    |
        3        2    4

Попробуйте вместо этого:

#include <stdio.h>

struct node {
    int data;
    struct node *fwd; //pointer to next node in the main list.
    struct node *down; //pointer to a linked list where this node is head.
};

struct node *solve(struct node *head) {
    struct node *temp = head, *fwd;
    while (temp != NULL) {
        fwd = temp->fwd;
        while (temp->down != NULL) {
            temp = temp->down;
        }
        temp->down = fwd;
        temp->fwd = NULL;
        temp = fwd;
    }
    return head;
}

int main(int argc, char **argv) {
    struct node
        n12 = { 12, NULL, NULL },
        n11 = { 11, NULL, &n12 },
        n10 = { 10, NULL, &n11 },
        n8 = { 8, NULL, NULL },
        n7 = { 7, &n10, &n8 },
        n9 = { 9, NULL, NULL },
        n6 = { 6, NULL, &n9 },
        n5 = { 5, &n7, &n6 },
        n4 = { 4, NULL, NULL },
        n3 = { 3, NULL, &n4 },
        n2 = { 2, NULL, &n3 },
        n1 = { 1, &n5, &n2 },
        *result = solve(&n1);

    while (result != NULL) {
        printf("%d%s", result->data, result->down ? " - " : "");
        result = result->down;
    }
    puts("");

    return 0;
}

Примечание: Это, конечно, не относится к node->down->fwd. Вы можете решить эту проблему с помощью рекурсивной функции, оставленной в качестве упражнения.

Answer 4

    struct node * last;
    void dfs(struct node * root)
    {
        if(root)
        {
            dfs(root->down);
            if(last!=NULL)
            {
                last->next=root->next;
                last=NULL;
            }
            dfs(root->next);
            if(root->down)
            root->next=root->down;

            if(root->next==NULL&&root->down==NULL)
                last=root;
        }
    }

Answer 5

Решение выглядит нормально для меня.Небольшое изменение может заключаться в том, что из диаграмм решения я бы ожидал, что ответом должен быть «горизонтальный» список (с использованием указателей fwd), а не вертикальный (с использованием указателей вниз), который ваше решение выдает