• 转载请注明作者和出处：http://blog.csdn.net/u011475210
• 代码地址：https://github.com/WordZzzz/Note/tree/master/LeetCode
• 刷题平台：https://www.nowcoder.com/ta/leetcode
• 题  库：Leetcode经典编程题
• 编  者：WordZzzz

题目描述

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.

解题思路

这道题剑指offer上应该也是有的，我就不去翻了。既然已经排序了，事情就变得简单多了，自下而上的归并排序的最后一步嘛~我们还是申请个新的结点，然后直接遍历两个链表元素比大小就好。

需要注意的是循环的终止条件，循环结束后还要把剩下的链表追加到cur的屁股后面哦。

C++版代码实现

/**
 * 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) {
        if(l1 == NULL)
            return l2;
        if(l2 == NULL)
            return l1;

        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～

完的汪(∪｡∪)｡｡｡zzz