合并两个有序链表,使得合并后的结果仍然是有序的,直观的做法就是从两个链表的首节点开始比较,将其中小的那个链接到新链表之中,(如果不想破坏原链表,那么需要将该节点拷贝一份,然后链接到新链表之中。)然后将该节点对应的原链表的遍历指针向后移动(p = p->next)一直这样比较下去,直到其中某个被遍历完,这时将剩余的那个链表直接链接到新链表后面即可。
当然,对于不带头结点的链表而言,需要判断原链表是否为空。带上头结点就可以适当的简化程序。
具体代码实现如下,这里的实现实在原链表上操作的,破坏了原链表,所以当你需要不破坏原链表的时候,那么你应该用malloc来申请一块内存存放原链表的节点。具体实现在此处不表。
#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<stdio.h>
//定义抽象数据类型
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); //构造链表
void Print(List L); //遍历链表
List Merge(List L1, List L2); //合并链表
int main()
{
List L1, L2, L;
//构造L1和L2链表
L1 = Read();
L2 = Read();
//合并L1和L2链表
L = Merge(L1, L2);
//合并后的结果
Print(L);
printf("\n");
Print(L1);
printf("\n");
Print(L2);
printf("\n");
system("pause");
return 0;
}
List Read()
{
int n;
scanf("%d", &n);
List p = (List)malloc(sizeof(struct Node)); //带头结点的链表
p->Next = NULL;
List temp1 = p;
for (int i = 0; i < n; i++) //构造链表
{
List temp = (List)malloc(sizeof(struct Node));
scanf("%d", &temp->Data);
temp1->Next = temp;
temp1 = temp1->Next;
}
temp1->Next = NULL; //链表结尾指向NULL
return p;
}
void Print(List L)
{
List temp = L->Next;
if (NULL == temp)
{
printf("空链表!");
}
while (NULL != temp)
{
printf("%d ",temp->Data);
temp = temp->Next;
}
}
List Merge(List L1, List L2)
{
List p = (List)malloc(sizeof(struct Node)); //带头结点的链表
List p1 = L1->Next;
List p2 = L2->Next;
List p3 = p;
while (NULL != p1 && NULL != p2) //合并
{
if (p1->Data <= p2->Data)
{
p3->Next = p1;
p3 = p3->Next;
p1 = p1->Next;
}
else
{
p3->Next = p2;
p3 = p3->Next;
p2 = p2->Next;
}
}
if (NULL == p1)
{
p3->Next = p2;
}
if (NULL == p2)
{
p3->Next = p1;
}
//此处在原节点的基础上合并两个链表,破坏掉了原链表,使得原链表为空
L1->Next = NULL;
L2->Next = NULL;
//返回新链表的头指针
return p;
}
这种使用双指针的方法,不止在合并链表的时候会用到,前面做删除数组中重复的元素时候,使用了相同的思路,快速排序也使用了类似的方式。这个双指针的用法还是很多的。
————————————————————9.16更新,并不华丽的分割线——————————————————
下面是链表相对于数组的一些特点。