17.12.31 链表合并

链表合并

描述
定义一种单向链表，链表结点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 3 5 3 2 4 6
例子输出
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……

谨记教诲

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。