How does C++ merge two sorted linked lists
This article mainly explains "C++ how to merge two sorted lists", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let Xiaobian take you to learn "C++ how to merge two sorted lists"!
Title Description:
Enter two incrementing lists, each of length n, merge the two lists so that the nodes in the new list are still incrementing sorted.
Data range: n is 0~1000, node value is-1000~1000
Time complexity O(n) and space complexity O(n)
For example, when {1,3,5},{2,4,6} are input, the merged linked list is {1,2,3,4,5,6}, so the corresponding output is {1,2,3,4,5,6}. The conversion process is as follows:
或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：
示例：
输入：
{1,3,5},{2,4,6}
返回值：
{1,2,3,4,5,6}
解题思路：
本题考察数据结构链表的使用。有两种解法：
遍历比较。建立一个新的头节点head后，用cur指针指向下一节点;然后依次比较两个子链表节点的值大小，谁小先塞谁，塞完就将其指向下一个节点;直到某个子链表遍历完，将cur的next指向没遍历完的那个链表当前的节点。
递归。从pHead1和pHead2的头节点开始比较，谁小就返回谁，然后其下一个指向，指向Merge函数的结果，Merge输入的两个链表为小的一方的next和大的一方的头节点，也就是用下一个值和它继续比谁更小;依次类推，递归中断的标志是有其中一个子链表指向nullptr，返回另一方即可。
测试代码：
解法一，遍历：
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode *head=new ListNode(-1); ListNode *cur=head; while(pHead1&&pHead2) { if(pHead1->valval) { cur->next=pHead1; pHead1=pHead1->next; } else{ cur->next=pHead2; pHead2=pHead2->next; } cur=cur->next; } cur->next=pHead1?pHead1:pHead2; return head->next; }};
解法二，递归：
/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(!pHead1) return pHead2; if(!pHead2) return pHead1; if(pHead1->valval) { pHead1->next=Merge(pHead1->next,pHead2); return pHead1; } else{ pHead2->next=Merge(pHead1,pHead2->next); return pHead2; } }};到此，相信大家对"C++怎么合并两个排序的链表"有了更深的了解，不妨来实际操作一番吧!这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习!
