链表合并
| 描述 | |
| 定义一种单向链表，链表结点LinkNode包含一个整数和一个指向下一个节点的指针。编写下面四个子函数： 1、建立链表: 从标准输入读取数据，并创建链表，返回创建的链表头 LinkNode *CreateLinkList(); 2、合并链表：参数是两个链表的头指针，返回合并后链表的头指针。合并后的链表仍然有序。 LinkNode *MergeLinkList(LinkNode *a, LinkNode *b); 3、遍历并显示合并后的链表的元素。 void DisplayLinkList(LinkNode *linklist); 4. 释放链表空间：如果CreateLinkList中使用了new分配空间，这里循环使用delete释放 void DestroyLinkList(LinkNode *linklist); 注意： 1. 假设用户输入数据时，是按照数据从小到大输入的，即链表是一个有序链表，不需要排序操作； 2. 没有按要求编写函数的，即使通过也会被扣分。 3. 你的程序应该使用尽可能少的内存空间。(在MergeLinkList函数中尽量不要分配新的LinkNode) | |
| 关于输入 | |
| 输入的第一行是一个整数m，代表第一个链表的元素个数（1 <= m <= 100000）； 第二行是m个整数，代表第一个链表的每个元素，题目保证m个整数从小到大排列。 第三行是一个整数n，代表第二个链表的元素个数（1 <= n <= 100000）； 第四行使n个整数，代表第二个链表的每个元素，题目保证n个整数从小到大排列。 | |
| 关于输出 | |
| 输出只有1行，输出以空格分隔的 m + n 个整数，按照从小到大的顺序排列。 | |
| 例子输入 | |
3 | |
| 例子输出 | |
1 2 3 4 5 6 |
1 #include<iostream>
2 using namespace std;
3 struct LinkNode
4 {
5 int n;
6 LinkNode *next;
7 };
8 LinkNode *CreateLinkList();//建立链表: 从标准输入读取数据，并创建链表，返回创建的链表头
9 LinkNode *MergeLinkList(LinkNode *, LinkNode *);//合并链表：参数是两个链表的头指针，返回合并后链表的头指针。合并后的链表仍然有序。
10 void DisplayLinkList(LinkNode *);//遍历并显示合并后的链表的元素。
11 void DestroyLinkList(LinkNode *);//释放链表空间：如果CreateLinkList中使用了new分配空间，这里循环使用delete释放
12 LinkNode *CreateLinkList()
13 {
14 int m;
15 cin >> m;
16 LinkNode *head;
17 head = new LinkNode;
18 LinkNode *tmp;
19 tmp = head;
20 for (int i = 0; i<m; i++)
21 {
22 int num;
23 cin >> num;
24 tmp->n = num;
25 if (i != m - 1)
26 {
27 tmp->next = new LinkNode;
28 if (i == 0)
29 head = tmp;
30 tmp = tmp->next;
31 }
32 else
33 tmp->next = NULL;
34 }
35 return head;
36 }
37 LinkNode *MergeLinkList(LinkNode *a, LinkNode *b)//将b并入a
38 {
39 LinkNode *tmp1 = a, *tmp2 = b,*tmp;
40 while (1)
41 {
42 if (tmp1->next != NULL)
43 {
44 if (tmp1->n<tmp2->n&&tmp1->next->n>tmp2->n)
45 {
46 tmp = tmp1->next;
47 tmp1->next = new LinkNode;
48 tmp1->next->n = tmp2->n;
49 tmp1->next->next = tmp;
50 tmp2 = tmp2->next;
51 if (tmp2 == NULL)
52 return a;
53 }
54 if (tmp1->next->n < tmp2->n)
55 {
56 tmp1 = tmp1->next;
57 }
58 if (tmp1->n > tmp2->n)
59 {
60 LinkNode *follow = new LinkNode;
61 follow->next = tmp1;
62 follow->n = tmp2->n;
63 a = follow;
64 tmp2 = tmp2->next;
65 tmp1 = a;
66 if (tmp2 == NULL)
67 return a;
68 }
69 }
70 else
71 {
72 if (tmp1->n > tmp2->n)
73 {
74 LinkNode *follow = new LinkNode;
75 follow->next = tmp1;
76 follow->n = tmp2->n;
77 a = follow;
78 tmp2 = tmp2->next;
79 tmp1 = a;
80 if (tmp2 == NULL)
81 return a;
82 }
83 else
84 {
85 tmp1->next = tmp2;
86 tmp2 = NULL;
87 return a;
88 }
89 }
90 }
91 }
92 void DisplayLinkList(LinkNode *linklist)
93 {
94 LinkNode *tmp = linklist;
95 cout << tmp->n;
96 tmp = tmp->next;
97 do {
98 cout << " " << tmp->n;
99 tmp = tmp->next;
100 } while (tmp != NULL);
101 }
102 void DestroyLinkList(LinkNode *linklist)
103 {
104 struct LinkNode* follow;
105 follow = linklist;
106 while (linklist != NULL)
107 {
108 linklist = linklist->next;
109 delete follow;
110 follow = linklist;
111 }
112 }
113 int main()
114 {
115 LinkNode *head1, *head2,*head;
116 head1 = CreateLinkList();
117 head2 = CreateLinkList();
118 head=MergeLinkList(head1, head2);
119 DisplayLinkList(head);
120 DestroyLinkList(head);
121 cout << endl;
122 return 0;
123 } View Code 大水题 然而讲链表的时候我完全睡着了
于是这道题成为了我有史以来WA最多的一次
之后一定要好好看PPT……
谨记教诲
转载于:.html
本文发布于:2024-02-01 02:18:37，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170672511733146.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
