功能将列表展平为单个列表

发布时间：2020-12-16 06:55:23 所属栏目：百科来源：网络整理

导读：给定一个链表结构,其中每个节点代表一个链表和包含两个类型的指针： (i)指向主列表中下一个节点的指针. (ii)指向此节点为head的链表的指针. 编写C函数以将列表展平为单个链表. 例如. 如果给定的链表是 1 -- 5 -- 7 -- 10 | | | 2 6 8 | | 3 9 | 4 然后将其

给定一个链表结构,其中每个节点代表一个链表和
包含两个类型的指针：

(i)指向主列表中下一个节点的指针.
(ii)指向此节点为head的链表的指针.

编写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;
 }

如果有的话,请通知我……欢迎其他解决方案和优化

解决方法

首先,让它运作起来很重要.由于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,&n12 },n10 = { 10,&n11 },n8 = { 8,n7 = { 7,&n10,&n8 },n9 = { 9,n6 = { 6,&n9 },n5 = { 5,&n7,&n6 },n4 = { 4,n3 = { 3,&n4 },n2 = { 2,&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.您可能希望使用递归函数来解决这个问题,该函数留作练习.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!