Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

C++代码如下:

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

//Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *p=NULL;
        //q始终记录l2中的元素,qq是取出来要插入到l1中的元素
        ListNode *q=NULL;
        ListNode *qq=NULL;
        //pre是p的前驱,插入比p小的元素时需要
        ListNode *pre=NULL;
        if(l1&&l2)
        {
            pre=p=l1;
            qq=q=l2;
            while(p&&q)
            {
                if(p->val<=q->val)
                {
                    pre=p;
                    p=p->next;
                }
                else
                {
                    qq=q;
                    q=q->next;
                    if(l1==p)
                    {
                        qq->next=l1;
                        l1=qq;
                        pre=p=l1;
                        continue;
                    }
                    qq->next=p;
                    pre->next=qq;
                    pre=qq;
                }
            }
            while(q)
            {
                pre->next=q;
                pre=q;
                q=q->next;
            }
        }
        if(l1==NULL)
            l1=l2;
        return l1;
    }
    void createList(ListNode *&head,int *arr)
    {
        ListNode *p=NULL;
        int i=0;
        for(i=0; i<5; i++)
        {
            if(head==NULL)
            {
                head=new ListNode(arr[i]);
                if(head==NULL)
                    return;
            }
            else
            {
                p=new ListNode(arr[i]);
                p->next=head;
                head=p;
            }
        }
    }
};

int main()
{
    Solution s;
    ListNode *L1=NULL;
    ListNode *L2=NULL;
    ListNode *L=NULL;
    int arr1[10]= {11,9,7,5,3};
    int arr2[10]= {10,8,6,4,2};
    s.createList(L1,arr1);
    s.createList(L2,arr2);
    L=s.mergeTwoLists(L1,L2);
    while(L)
    {
        cout<<L->val<<" ";
        L=L->next;
    }
}

运行结果:

第二遍:

class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1==NULL)
            return l2;
        if(l2==NULL)
            return l1;
        ListNode *head=NULL;
        ListNode *r=NULL;
        ListNode *p=l1;
        ListNode *q=l2;
        if(p->val<q->val)
        {
            head=p;
            r=head;
            p=p->next;
        }
        else
        {
            head=q;
            r=head;
            q=q->next;
        }
        r->next=NULL;
        while(p&&q)
        {
            if(p->val<q->val)
            {
                r->next=p;
                r=p;
                p=p->next;
            }
            else
            {
                r->next=q;
                r=q;
                q=q->next;
            }
            r->next=NULL;
        }
        if(q)
            p=q;
        r->next=p;
        return head;
    }
};

 

时间: 2024-09-26 14:29:30

Merge Two Sorted Lists的相关文章

LeetCode 23 Merge k Sorted Lists(合并K个已排序链表)

翻译 合并K个已排序的链表,并且将其排序并返回. 分析和描述其复杂性. 原文 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 代码 我们采用分治的方法来解决这个问题,其有K个链表,不断将其划分(partition),再将其归并(merge). 划分的部分并不难,将其不断分成两部分,但是需要注意的是可能出现start和end相等的情况,这时候就直接r

[LeetCode]21.Merge Two Sorted Lists

[题目] Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. [分析] 无 [代码] /********************************* * 日期:2015-01-06 * 作者:SJF0115 * 题目: 21.Merge Two Sorted L

[LeetCode]23.Merge k Sorted Lists

[题目] Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. [分析] 无 [代码] /********************************* * 日期:2015-01-06 * 作者:SJF0115 * 题目: 23.Merge k Sorted Lists * 来源:https://oj.leetcode.com/problems/me

LeetCode 21 Merge Two Sorted Lists(合并两个已排序的数组)

翻译 合并两个排好序的链表,并返回这个新链表. 新链表应该由这两个链表的头部拼接而成. 原文 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. 代码 /** * Definition for singly-linked list. * struct ListNode

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 思路:开始做过两两合并的链表,此时做k路合并,即将k个链表进行合并,可以先将这k个链表进行两两合并,知道合并为一个链表.直接调用前面写过的两两合并的例子.   C++代码实现: #include<iostream> #include<new> #include<vector>

Java&amp;amp;quot;merge two sorted lists into a new sorted one&amp;amp;quot;

问题描述 seekhelp!howcanIcreate"publicstaticSortedListmergeList(SortedListlist1,SortedListlist2)"methodThismethodcanmergetwosortedlistsintoanewsortedone,andreturnareferenceofthenewlist.Theprogramshouldgothrougheachlinkiteminbothlists,anddirectlylink

&lt;font color=&quot;red&quot;&gt;[置顶]&lt;/font&gt;

Profile Introduction to Blog 您能看到这篇博客导读是我的荣幸,本博客会持续更新,感谢您的支持,欢迎您的关注与留言.博客有多个专栏,分别是关于 Windows App开发 . UWP(通用Windows平台)开发 . SICP习题解 和 Scheme语言学习 . 算法解析 与 LeetCode等题解 . Android应用开发 ,而最近会添加的文章将主要是算法和Android,不过其它内容也会继续完善. About the Author 独立 Windows App 和

[经典面试题][暴风影音]暴风影音2014校招笔试题

合并两个已经排序的单链表为一个排序的单链表,相同内容只保留一个如:单链表a:1->2->3->4 单链表b:3->4->5 输出:1->2->3->4->5 具体参考:[LeetCode]21.Merge Two Sorted Lists /*--------------------------------------------- * 日期:2015-02-23 * 作者:SJF0115 * 题目: 合并排序链表 * 来源:暴风影音 * 博客: --

[LeetCode]148.Sort List

[题目] Sort a linked list in O(n log n) time using constant space complexity. [分析] 单链表适合用归并排序,双向链表适合用快速排序.本题可以复用Merge Two Sorted Lists方法 [代码] /********************************* * 日期:2015-01-12 * 作者:SJF0115 * 题目: 148.Sort List * 来源:https://oj.leetcode.c