#AcWing--合并两个排序的链表

 题目

36. 合并两个排序的链表 - AcWing题库https://www.acwing.com/problem/content/description/34/

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围

链表长度 [0,500][0,500]。

样例

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

 法一：(二路归并) O(n)

1.设定一个头节点为head的新链表用于存储合并后的链表。（头结点不存储链表数据，只是为了定位到新链表）

2.通过比较两链表结点中val的大小选择连接次序。

3.当某条链表遍历到结尾时即可停止比较，同时将另外一条链表剩余部分链接在新链表后即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* head=new ListNode(0);
        ListNode* cur=head;
        while(l1!=NULL&&l2!=NULL){
            if(l1->val<=l2->val) {cur->next=l1->val;l1=l1->next;}
            else {cur->next=l2->val;l2=l2->next;}
            cur=cur->next;
        }
        cur->next=(val->next!=NULL?l1->next:l2->next);
        return head->next;
    }
};

 

 法二：递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        if(l1->val <= l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        } else {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }
};