剑指offer（16）——C++实现两个链表合并

朴灿烈づ我的快乐病毒、 2024-04-17 05:31 23阅读 0赞

# 题目 #

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

# 考察点 #

*  链表

# 解题思路 #

*  递归实现，比较每个节点大小，将较小的放入新链表
 *  非递归，原理同上

# 完整代码 #

/*16-合并两个链表*/
    #include<iostream>
    #include<queue>
    using namespace std;
    struct ListNode {
        
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
        
    	}
    };
    class Solution {
        
    public:
     
    	//递归实现 ，合并与排序一起进行
    	ListNode* Merge2(ListNode* pHead1, ListNode* pHead2)
    	{
        
    		ListNode* ListMerge;
    		if (pHead1 == NULL)
    			return pHead2;//???ListMerge = pHead2;会产生堆栈溢出
    		if (pHead2 == NULL)
    			return pHead1;//????ListMerge = pHead1;
    		//针对每一个节点进行比较
    		if (pHead1->val > pHead2->val)
    		{
        
    			ListMerge = pHead2;///将较小的赋值给要输出的链表
    			ListMerge->next = Merge2(pHead1, pHead2->next);//继续对pHead1.pHead2的下一位进行递归，赋值给要输出的链表的下一位
    		}
    		else
    		{
        
    			ListMerge = pHead1;
    			ListMerge->next = Merge2(pHead1->next, pHead2);
    		}
    		return ListMerge;
    	}
    };
    int main()
    {
        
    	ListNode *p1 = new ListNode(1); ListNode *p2 = new ListNode(3); ListNode *p3 = new ListNode(5);
    	ListNode *p4 = new ListNode(2); ListNode *p5 = new ListNode(4); ListNode *p6 = new ListNode(6);
    	p1->next = p2; p2->next = p3;  p4->next = p5; p5->next = p6;
    	Solution s;
    	ListNode* result;
    	result = s.Merge(p1, p4);
    	//result = s.Merge2(p1, p4);
    	//打印链表
    	queue<ListNode*> res;
    	ListNode* Node = result;
    	while (Node != NULL)//压入队列
    	{
        
    		res.push(Node);
    		Node = Node->next;
    	}
    	while (!res.empty())//出队列
    	{
        
    		Node = res.front();
    		cout << Node->val << ' ';
    		res.pop();
    
    	}
    	return 0;
    }

# 编程问题 #

*  链表的打印：顺序打印可用队列实现；逆序可用栈实现；
 *  返回值问题: 原因目前未知。

if (pHead1 == NULL)
    			return pHead2;//???ListMerge = pHead2;会产生堆栈溢出
    		if (pHead2 == NULL)
    			return pHead1;//????ListMerge = pHead1;