首页 > 试题广场 >

请实现一个函数，把两个从大到小的有序链表合并成一个链表，新的

[问答题]

请实现一个函数，把两个从大到小的有序链表合并成一个链表，新的链表是一个从小到大的有序链表。

struct list
{
    int value;
    list* next;
};
list * merge (list *list1_head, list*list2_head);

柏拉图个啥

    list *merge(list *list1_head,list *list2_head)
    {
        list *newlist = NULL;
        list *current = NULL;
        while(NULL!=list1_head && NULL!=list2_head)
        {
            if(list1_head->value > list2_head->value)
            {
                current = list1_head->next;
                list1_head->next = newlist;
                newlist = list1_head;
                list1_head = current;
            }
            else
            {
                current = list2_head->next;
                list2_head->next = newlist;
                newlist = list2_head;
                list2_head = current;
            }
        }

        while(NULL!=list1_head)
        {
            current = list1_head->next;
            list1_head->next = newlist;
            newlist = list1_head;
            list1_head = current;
        }
        while(NULL!=list2_head)
        {
            current = list2_head->next;
            list2_head->next = newlist;
            newlist = list2_head;
            list2_head = current;
        }
        return newlist;
    }

发表于 2015-03-29 11:41:27 回复(0)

血江南

/*请实现一个函数，把两个从大到小的有序链表合并成一个链表，
新的链表是一个从小到大的有序链表。*/
#include<iostream>
#include<string>
#include<vector>
using namespace std;
struct list
{
    int value;
    list* next;
};
void initList(list **head){
    //位头结点开辟空间
    *head = new list;
    (*head)->value=-1; // 头结点不存放
    (*head)->next=NULL;
}
void insert(list *head, int elem){
    list *p=head;
    list *q=new list;
    q->value=elem;
    q->next=NULL;
    while (p->next)
    {
        p=p->next;
    }
    p->next = q;
}
void displaylist(list *head){
    list *p=head;
    while (p->next)
    {
        cout << p->next->value << "->";
        p=p->next;
    }
    cout<<endl;
}
list * merge(list *list1_head, list*list2_head)
{
    //头结点指向大的
    list *head=new list;
    head->next=NULL;
    head->value = -1;
    list *p=head;

list *p1=list1_head;
list *p2=list2_head;

while (p1&&p2)
{

        if (p1->value >= p2->value){
            list *q=new list;
            q->next=NULL;
            q->value=p1->value;
            p->next=q;
            p=p->next;
            p1=p1->next;
            if (p1==NULL)
                    break;
        }
        if (p1->value < p2->value){
            list *q = new list;
            q->next = NULL;
            q->value = p2->value;
            p->next = q;
            p = p->next;
            p2 = p2->next;

            if (p2==NULL)
                    break;
        }
    }
    if(p1)
    {
        p->next=p1;
    }
    if (p2)
    {
        p->next=p2;
    }

    return head;
}
//将链表第m到n个结点反转
list *Reverse(list *head, int m, int n){
    list *dummy=new list;
    dummy->next=head;

    //prev是需要反转的第一个结点的前一个结点
    list *prev=dummy;
    for (int i = 0; i < m - 1; i++){
        prev=prev->next;
    }

    list *head2=prev;
    prev=prev->next;     //第一个结点
    list *q=prev->next;
    for (int i = m; i < n; i++){
        prev->next=q->next;
        q->next=head2->next;head2->next=q;
        q=prev->next;
    }
    return dummy;
}

int main(){
    int a1[5] = {12,8,3,1,0};
    int a2[7] = {19,16,9,4,2,1,0};
    list *head1,*head2;
    initList(&head1); initList(&head2);
    for (int i = 0; i < 5; i++){
        insert(head1, a1[i]);
    }
    displaylist(head1);

    for (int i = 0; i < 7; i++){
        insert(head2, a2[i]);
    }
    displaylist(head2);

    list *head=merge(head1->next,head2->next);
    displaylist(head);

    list*h = Reverse(head->next,1,12);
    displaylist(h);

system("pause");
return 0;
}

发表于 2016-06-03 11:04:29 回复(0)

manhua


	structlist1



	{  



	  intvalue;



	 list1* next;



	};



	list1 * merge (list1 *list1_head, list1 *list2_head)



	{



	    list1* head=NULL,*p=NULL;



	    if(list1_head->value<list2_head->value)



	    {   head=list1_head;list1_head=list1_head->next;}



	    else



	    {  head=list2_head;list2_head=list2_head->next;}



	    p=head;



	    while(list1_head&&list2_head)



	    {



	        if(list1_head->value<list2_head->value)



	        {   head->next=list1_head;head=list1_head;list1_head=list1_head->next;}



	        else



	        {  head->next=list2_head;head=list2_head;list2_head=list2_head->next;}



	    }



	    if(list2_head==NULL&&list1_head==NULL)



	        return p;



	    if(!list2_head)



	        head->next=list1_head;



	    if(!list1_head)



	        head->next=list2_head;



	    return p;



	}

编辑于 2015-10-09 15:14:22 回复(0)

疯行田下

//反转链表
ListNode* ResverseList(ListNode* head)
{
if (head == nullptr || head->m_pNext == nullptr)
{
return head;
}

ListNode *pre, *curr,*nextNode;
pre = nullptr;
curr = head;
while (curr != nullptr)
{
nextNode = curr->m_pNext;
curr->m_pNext = pre;
pre = curr;
curr = nextNode;
}
return pre;
}
//合并两个从大到小的链表，为一个从小到大的链表
ListNode* MergeTwoOpp(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == nullptr)
return ResverseList(pHead2);
if(pHead2 == nullptr)
return ResverseList(pHead1);

ListNode* pNode = nullptr;
//ListNode* pPrev1 = nullptr;
ListNode* pNext1 = nullptr,* pNext2 = nullptr;

if(pHead1->m_nValue > pHead2->m_nValue)
{
pNode = pHead1;
pHead1 = pHead1->m_pNext;
pNext1 = pHead1;
pNode->m_pNext =nullptr;
}
else
{
pNode = pHead2;
pHead2 = pHead2->m_pNext;
pNext2 = pHead2;
pNode->m_pNext =nullptr;
}

//ListNode* pNode = pOppHead;

while(pHead1 != nullptr && pHead2 != nullptr)
{
if(pHead1->m_nValue > pHead2->m_nValue)
{
pNext1 = pHead1->m_pNext;
pHead1->m_pNext = pNode;
pNode = pHead1;
pHead1 = pNext1;
}
else
{
pNext2 = pHead2->m_pNext;
pHead2->m_pNext = pNode;
pNode = pHead2;
pHead2=pNext2;
}
}
ListNode* pOppNode = pNode;

if (pHead1 != nullptr)
{
ListNode * p1 = ResverseList(pHead1);
pOppNode = p1;
while (p1->m_pNext != nullptr)
p1 = p1->m_pNext;
p1->m_pNext = pNode;
}
if (pHead2 != nullptr)
{
ListNode * p2 = ResverseList(pHead2);
pOppNode = p2;
while (p2->m_pNext != nullptr)
p2 = p2->m_pNext;
p2->m_pNext = pNode;
}
return pOppNode;
}

编辑于 2015-06-18 21:12:18 回复(0)

henghengbiang

list * merge(list *list1_head, list*list2_head)
{
    if (list1_head == NULL)
    {
        return list2_head;
    }
    if (list2_head == NULL)
    {
        return list1_head;
    }
    list *list3_head = NULL;
    list *p1 = list1_head;
    list *p2 = list2_head;
    list *pNext;

    while (p1 != NULL&&p2 != NULL)
    {
        if (p1->data < p2->data)
        {
            pNext = p2->next;
            p2->next = list3_head;
            list3_head = p2;
            p2 = pNext;
        }
        else
        {
            pNext = p1->next;
            p1->next = list3_head;
            list3_head = p1;
            p1 = pNext;
        }
    }
    while (p1 != NULL)
    {
        pNext = p1->next;
        p1->next = list3_head;
        list3_head = p1;
        p1 = pNext;
    }
    while (p2 != NULL)
    {
        pNext = p2->next;
        p2->next = list3_head;
        list3_head = p2;
        p2 = pNext;
    }

    return list3_head;
}

发表于 2015-05-07 15:04:15 回复(0)

mainliang

list * merge (list *list1_head, list*list2_head)
{
    
}

发表于 2014-12-26 20:30:35 回复(0)

牛客177648号

归并排序法.

发表于 2014-11-14 13:31:03 回复(0)

jlstmac

稍微修改了一下：

list* merge(list *list1_head, list *list2_head){

list* pRet = NULL;

while(list1_head!= NULL || list2_head!= NULL){

list* node = new list;

node->next = NULL;

if( ( list2_head != NULL && list1_head != NULL && (list1_head->value > list2_head->value)) || (!list2_head && list1_head)){

node->value = list1_head->value;

list1_head = list1_head->next;

}else{

node->value = list2_head->value;

list2_head = list2_head->next;

}

node->next = pRet;

pRet = node;

}

return pRet;

}

发表于 2014-11-05 15:56:16 回复(0)

提交观点

问题信息

C++工程师链表 C++ 迅雷 2013

来自：迅雷2013C++笔试卷B

上传者：小咚

难度：

8条回答 19收藏 7837浏览

请实现一个函数，把两个从大到小的有序链表合并成一个链表，新的

问题信息

热门推荐

相关试题