C语言经典例74-连接两个链表

深藏阁楼爱情的钟 2023-07-06 11:41 82阅读 0赞

### 目录 ###

*  1 题目
 *  2 分析
 *  3 实现
 *  4 运行结果

# 1 题目 #

连接两个链表，如有链表`A`和链表`B`，将链表`B`按原顺序接在链表`A`后面，链表结构为：

typedef int ElementType;
    typedef struct node { 
        ElementType data;
        struct node *Next;
    } *List;

# 2 分析 #

本题在逻辑上很简单，不难想出只要得到链表`A`的最后一个节点指针，然后将其指向链表`B`的第一个节点即可，注意创建链表时，链表带头节点，实际上链表`B`的第一个节点为链表`B`的头节点的下一个节点`B->Next`（程序的第`57`行）。

# 3 实现 #

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <unistd.h>
    
    typedef int ElementType;
    typedef struct node { 
        ElementType data;
        struct node *Next;
    } *List;
    
    // 创建链表
    List CreateList(void) { 
        List L = (List)malloc(sizeof(struct node));
        L->data = 0;
        L->Next = NULL;
        return L;
    }
    
    // 初始化链表节点数据
    void InitList(List L) { 
        srand((unsigned)time(NULL)); // 随机数种子
        for (int i = 0; i < 10; i++) { 
            List p = (List)malloc(sizeof(struct node));
            p->data = rand() % 100; // 节点数据为随机数，随机数范围为0~99
            p->Next = L->Next;
            L->Next = p;
        }
    }
    
    // 打印链表
    void PrtList(List L) { 
        List p = L->Next;
        while (p) { 
            printf("%d ", p->data);
            p = p->Next;
        }
        printf("\n");
    }
    
    int main(void) { 
    	List A = CreateList();
    	InitList(A);
    	sleep(1); // 延迟一秒，需要头文件 unistd.h
    	List B = CreateList();
    	InitList(B);
    	printf("链表A为：");
    	PrtList(A);
    	printf("链表B为：");
    	PrtList(B);
    	// 找到链表A的最后一个节点
    	List tmp = A;
    	while (tmp->Next != NULL) { 
    		tmp = tmp->Next;
    	}
    	// 连接A和B，注意链表是带头结点的，连接时要忽略B的头结点，从第一个节点开始
    	tmp->Next = B->Next;
    	printf("连接后为：");
    	PrtList(A);
        return 0;
    }

# 4 运行结果 #

链表A为：73 12 57 72 51 71 11 56 48 30
    链表B为：25 56 30 84 78 85 7 52 96 33
    连接后为：73 12 57 72 51 71 11 56 48 30 25 56 30 84 78 85 7 52 96 33