合并两个有序链表

恋喵大鲤鱼

发布于 2018-08-03 11:00:01

2.3K0

发布于 2018-08-03 11:00:01

文章被收录于专栏：C/C++基础

1.题目要求

这是一道求职面试时经常要求手写或者机试的经典题目。

已知两个链表head1和head2各自有序，请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点，即使节点值相同。

注意：不能开辟新空间来存储合并后的链表。如果第一次做该题，很容易会想到使用新链表来存储合并后的有序链表。虽然可以如此实现，但是不符合常规解法和面试官的要求。

2.非递归实现

算法过程：输入：两个有序的单链表head1与head2；输出：合并后的有序单链表mergeHead；算法描述：（1）如果head1或head2为空链表，则直接返回另外一个链表；（2）选择head1与head2链表当前节点值较小的节点，挂接到后并后的链表mergeHead；（3）重复步骤2，直到链表head1或者head2遍历完成，未遍历完的链表，直接挂接到mergeHead的尾节点。

具体实现如下：

#include <sstream>
#include <iostream>
using namespace std;

struct ListNode  
{  
    int         value;  
    ListNode*   next;
    ListNode()  {value=0;next=NULL;}
    ListNode(int value,ListNode* next = NULL):value(value),next(next){}  
};

//@brief:非递归实现两个有序单链表
//@注意：两个链表需要从小到大顺序排列
ListNode* mergeOrderedLinkedList(ListNode* head1,ListNode* head2)
{
    if (head1 == NULL)  
    {  
        return head2;  
    }
    else if(head2 == NULL)  
    {  
        return head1;  
    }

    ListNode* mergeHead = NULL;  
    if (head1->value<head2->value)  
    {  
        mergeHead=head1;
        head1=head1->next;
    }  
    else  
    {  
        mergeHead = head2;  
        head2 = head2->next;  
    }  
    ListNode* tmpNode = mergeHead;  
    while(head1&&head2)
    {  
        if(head1->value<head2->value)  
        {  
            mergeHead->next = head1;  
            head1 = head1->next;  
        }  
        else  
        {  
            mergeHead->next = head2;  
            head2 = head2->next;  
        }  
        mergeHead = mergeHead->next;  
    }  
    if (head1)
    {  
        mergeHead->next = head1;  
    }  
    if (head2)  
    {  
        mergeHead->next = head2;  
    }

    return tmpNode;  
}

//打印链表
void printLinkedList(ListNode* head)
{
    while(head)
    {
        cout<<head->value<<" ";
        head=head->next;
    }
    cout<<endl;
}

int main(int argc,char* argv[])
{
    ListNode* head1=NULL,*curList1=NULL,*head2=NULL,*curList2=NULL;
    string strIn;
    int value;

    cout<<"创建链表1，从小到大顺序输入链表1："<<endl;
    getline(cin,strIn);
    stringstream ss(strIn);
    cout<<"ss0 strIn:"<<ss.str()<<endl;
    while(ss>>value)        //从string中按照空格读取int
    {
        ListNode* newNode1=new ListNode;
        newNode1->value=value;
        if(head1==NULL && curList1==NULL)
        {
            head1=newNode1;
            curList1=newNode1;
        }
        else
        {
            curList1->next=newNode1;
            curList1=curList1->next;
        }
    }

    cout<<"创建链表2，从小到大顺序输入链表2："<<endl;
    getline(cin,strIn);
    ss.clear();  //清空状态
    ss.str("");  //清空内容
    ss<<strIn;   //重新输出至string
    cout<<"ss1 strIn:"<<ss.str()<<endl;
    while(ss>>value)        //从string中按照空格读取int
    {
        ListNode* newNode2=new ListNode;
        newNode2->value=value;
        if(head2==NULL && curList2==NULL)
        {
            head2=newNode2;
            curList2=newNode2;
        }
        else
        {
            curList2->next=newNode2;
            curList2=curList2->next;
        }
    }

    //合并两个有序链表
    ListNode* mergeHead=mergeOrderedLinkedList(head1,head2);

    //打印链表
    cout<<"合并后链表："<<endl;
    printLinkedList(mergeHead);
}

运行程序，输出结果：

从小到大顺序输入链表1：
1 2 3 5
ss0 strIn:1 2 3 5
从小到大顺序输入链表2：
3 4 5 6 7 8
ss1 strIn:3 4 5 6 7 8
合并后链表：
1 2 3 3 4 5 5 6 7 8

3.递归实现

从上面合并两个有序链表的步骤中可以看出，每次合并的步骤（2）都是一样的，由此我们想到了递归。具体实现如下：

//@brief:递归实现两个有序单链表
//@注意：两个链表需要从小到大顺序排列
ListNode* mergeOrderedLinkedListRecursion(ListNode* head1,ListNode* head2)
{
    if(head1 == NULL)  
    {  
        return head2;  
    }
    else if(head2 == NULL)  
    {  
        return head1;  
    }

    ListNode* mergeHead = NULL;
    if(head1->value<head2->value)  
    {
        mergeHead=head1;
        mergeHead->next=mergeOrderedLinkedListRecursion(head1->next,head2);
    }
    else
    {
        mergeHead=head2;
        mergeHead->next=mergeOrderedLinkedListRecursion(head1,head2->next);
    }
    return mergeHead;
}