C++解决合并两个排序的链表问题

题目描述：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： n为0~1000，节点值为-1000~1000

要求：空间复杂度 o(1)，时间复杂度 o(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-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}

解题思路：

本题考察数据结构链表的使用。有两种解法：

1. 遍历比较。建立一个新的头节点head后，用cur指针指向下一节点；然后依次比较两个子链表节点的值大小，谁小先塞谁，塞完就将其指向下一个节点；直到某个子链表遍历完，将cur的next指向没遍历完的那个链表当前的节点。
2. 递归。从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->val<=phead2->val)
            {
                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->val<=phead2->val)
        {
            phead1->next=merge(phead1->next,phead2);
            return phead1;
        }
        else{
            phead2->next=merge(phead1,phead2->next);
            return phead2;
        }
    }
};

到此这篇关于c++解决合并两个排序的链表问题的文章就介绍到这了,更多相关c++ 合并两个排序的链表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！