leetcode--21--合并两个有序链表

题目：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

思路：
1、同时遍历两个链表，比较两个链表的首位元素，将较小的放入结果链表中

Python代码：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        elif not l2:
            return l1
        
        ret = ListNode(0)
        guard = ret
        while l1 and l2:
            if l1.val<l2.val:
                guard.next = l1
                l1 = l1.next if l1.next else None
            else:
                guard.next = l2
                l2 = l2.next if l2.next else None
            guard = guard.next
        if not l2:
            guard.next = l1
        if not l1:
            guard.next = l2

        return ret.next
        

Python代码2：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l = ListNode(0)
        guard = l

        while l1 and l2:
            if l1.val>=l2.val:
                item = ListNode(l2.val)
                l.next = item
                l2 = l2.next
            else:
                item = ListNode(l1.val)
                l.next = item
                l1 = l1.next
            l = l.next
        if l1:
            l.next = l1
        if l2:
            l.next = l2
        return guard.next

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) {
        ListNode* ret = new ListNode(0);
        ListNode* guard = ret;
        while (l1!=nullptr && l2!=nullptr){
            if(l1->val<l2->val){
                guard->next = l1;
                l1 = l1->next;
            }else{
                guard->next = l2;
                l2 = l2->next;
            }
            guard = guard->next;
        }
        if(l1!=nullptr){
            guard->next = l1;
        }else{
            guard->next = l2;
        }
        return ret->next;
    }
};

C++代码2:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* guard = new ListNode(0);
        ListNode* l = guard;

        while (l1!=nullptr && l2!=nullptr){
            if(l1->val>=l2->val){
                ListNode* item = new ListNode(l2->val);
                l->next = item;
                l2 = l2->next;
            }else{
                ListNode* item = new ListNode(l1->val);
                l->next = item;
                l1 = l1->next;
            }
            l = l->next;
        }
        if(l1!=nullptr){
            l->next = l1;
        }
        if(l2!=nullptr){
            l->next = l2;
        }
        return guard->next;
    }
};

思路2：
1、使用递归的写法，遍历两个链表，将较小的节点值作为当前节点，将较小的节点后面的节点和另一个链表作为函数的参数进行递归调用

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 || !l2) return l1 ? l1 : l2;

        if(l1->val<l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};