题目描述

 

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

示例：

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

 

解题思路

 

首先找到新链表头节点，即两个链表头节点值较小的节点，然后以头节点所在链表为准，依次将另一个链表插入到对应位置中。

 

代码

 

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {12         if(l1 == NULL) return l2;13         if(l2 == NULL) return l1;14         if(l1->val > l2->val)15             return mergeTwoLists(l2, l1);16         ListNode* head = l1;17         while(l1->next && l2){18             if(l1->next->val > l2->val){19                 ListNode* next = l2->next;20                 l2->next = l1->next;21                 l1->next = l2;22                 l2 = next;23             }24             l1 = l1->next;25         }26         if(l2) l1->next = l2;27         return head;28     }29 };