美文网首页LeetCode
Leetcode 21— Merge Two Sorted Li

Leetcode 21— Merge Two Sorted Li

作者: 帅气的昵称都有人用了 | 来源:发表于2018-10-29 11:22 被阅读0次

    题目描述

    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.

    Example:
    Input: 1->2->4, 1->3->4
    Output: 1->1->2->3->4->4

    哈,终于到了数据结构的问题了,而且这道数据结构体还是一道非常简单的数据结构问题,我们在这里使用的是尾插法进行操作,我们要知道头插法是一个逆序,而头插法是一个顺序的问题,因此根据题目要求选择了头插法,具体实现也很简单,顺着头插法的思路走就可以,如果l1中的节点大小要小于l2的话,那么就把l1中的那个节点放进去即可,最后如果其中一个链表已经为空,那么直接将另外一个链表接到后面就可以了,基本操作:

    /**
     * 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,*q,*r;
            ListNode* l3=new ListNode(-1);
            p=l1;
            q=l2;
            r=l3;
            while(p!=nullptr&&q!=nullptr)
            {
                if(p->val<=q->val)
                {
                    r->next=p;
                    r=r->next;
                    p=p->next;
                }else{
                    r->next=q;
                    r=r->next;
                    q=q->next;
                }
            }
            r->next=nullptr;
            if(p!=nullptr)
            {
                r->next=p;
            }
            if(q!=nullptr)
            {
                r->next=q;
            }
            return l3->next;
        }
    };
    

    运行成功,而且运行时间8ms,还是很不错的,这是基本操作啊。

    但是这一种解法可能不能满足,因此我在网上又发现了另外的一个思路,是使用递归的方法。

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if (!l1) return l2;
            if (!l2) return l1;
            ListNode *head = l1->val < l2->val ? l1 : l2;
            ListNode *nonhead = l1->val < l2->val ? l2 : l1;
            head->next = mergeTwoLists(head->next, nonhead);
            return head;
        }
    };
    

    不过好像运行效果是12ms,但是代码上简洁了很多啊

    相关文章

      网友评论

        本文标题:Leetcode 21— Merge Two Sorted Li

        本文链接:https://www.haomeiwen.com/subject/lzxbtqtx.html