c - 将列表展平为单个列表的函数

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

首先让它发挥作用很重要。由于 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。您可能想使用递归函数来解决这个问题，这留作练习。