亲宝软件园·资讯

展开

C++ 合并两个排序的链表

翟天保Steven 人气:0

题目描述:

输入两个递增的链表,单个链表的长度为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;
        }
    }
};

加载全部内容

相关教程
猜你喜欢
用户评论