网站开发是什么工作,ui做的好的公司网站,wordpress toggle,wordpress点击量改热度合并两个有序链表是c语言数据结构中比较经典的问题#xff0c;首先两个链表都是有序的#xff0c;即节点的顺序是按照各个节点中的值从小到大排序#xff0c;而且合并之后的新链表中的各个节点顺序也要满足从小到大的排序#xff0c;具体如下图所示。 思路#xff1a;用ma… 合并两个有序链表是c语言数据结构中比较经典的问题首先两个链表都是有序的即节点的顺序是按照各个节点中的值从小到大排序而且合并之后的新链表中的各个节点顺序也要满足从小到大的排序具体如下图所示。 思路用malloc申请一个哨兵位的头节点NewHead作为合并之后新链表的头节点注意此头节点的作用是作为一个哨兵最后用完要将其释放。再定义三个指针指针1用来遍历链表1中的节点指针2遍历链表2中的节点指针3则用来维护合并之后的新链表。将指针1指向的节点与指针2指向的节点进行值的比较小的一方则把节点“给到”NewHead节点的下一个节点并且移动指针3往后走继续维护下一个节点。 若List1和List2中有一个指针已经遍历到空则直接将另一条链表剩余节点都连接到tail指向的节点后面也就是将没有指向空的指针给到了tail维护的节点的next。 最后合并链表的任务完成后对newhead哨兵位的头节点进行释放并且要记住newhead节点的下一个节点的位置因为该位置才是合并后链表的真正意义上的头节点的地址。 测试代码实现如下代码包括创建链表、打印链表、测试合并链表的功能
#includestdio.h
#includestdlib.htypedef struct ListNode //创建节点结构体
{int data;struct ListNode* next;
}LNode;void Print(LNode* phead)//打印函数
{LNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL);//模拟链表最后指向的是NULL
}LNode* mergeTwoLists(LNode* list1, LNode* list2) {LNode* head NULL;//记住合并后链表的头节点LNode* tail NULL;//用于遍历合并后的链表head tail (LNode*)malloc(sizeof(LNode));//创建一个头节点newheadwhile (list1 list2)//若有一个指针为空则跳出循环{if (list1-data list2-data)//数据小的节点给到tail{tail-next list2;list2 list2-next;}else{tail-next list1;list1 list1-next;}tail tail-next;//更新tail的位置以便下一次节点的插入}if (list1)//若list1指针不为空则说明list2指针为空则直接将list1指向的节点给到tail{tail-next list1;}else//反之若list2指针不为空则说明list1指针为空则直接将list2指向的节点给到tail{tail-next list2;}LNode* poi head;//记住头节点的位置因为准备释放申请的头节点的空间//因为最终返回是不带哨兵位节点的链表head head-next;//head指向哨兵位节点的下一个节点该节点才是合并链表后真正的头节点free(poi);//释放申请的空间return head;//返回合并后链表的头节点的地址
}
int main()
{//链表List1LNode* n1 (LNode*)malloc(sizeof(LNode));//创建3个节点LNode* n2 (LNode*)malloc(sizeof(LNode));LNode* n3 (LNode*)malloc(sizeof(LNode));LNode* plist1 n1;//指向List1的头指针plist1n1-data 1;//给每个节点都赋值n2-data 2;n3-data 4;n1-next n2;//手动构建链表n2-next n3;n3-next NULL;//链表List2LNode* n4 (LNode*)malloc(sizeof(LNode));//创建3个节点LNode* n5 (LNode*)malloc(sizeof(LNode));LNode* n6 (LNode*)malloc(sizeof(LNode));LNode* plist2 n4;//指向List2的头指针plist2n4-data 1;//给每个节点都赋值n5-data 3;n6-data 4;n4-next n5;//手动构建链表n5-next n6;n6-next NULL;printf(List1:);Print(plist1);//打印链表1printf(\nList2:);Print(plist2);//打印链表2printf(\n合并后);LNode* newhead mergeTwoLists(plist2, plist1);//合并函数Print(newhead);//打印合并后的链表return 0;
} 运行结果 结语 合并链表的方法如上希望本文可以对你起到帮助 ︶↗
