Leetcode 21— Merge Two Sorted Li

题目描述

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，但是代码上简洁了很多啊