将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4因为之前做过两数之和的那道题，所以一开始并没有审清楚题，这个题的后一句提示很重要，是直接拼接两个链表的所有节点，也就是说其实不需要建立新的链表，只需要对这两个链表进行排序即可。所以思路就是重新对链表的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 * l3 = new ListNode(0); //ListNode l3(0); ListNode * curr = l3; while(l1!=NULL&&l2!=NULL) { if(l1->val>l2->val) { curr->next = l2; l2 = l2->next; } else { curr->next = l1; l1 = l1->next; } curr = curr->next; } if (l1!=NULL) curr->next = l1; if (l2!=NULL) curr->next = l2; return l3->next; } };python3源代码：
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ l3 = ListNode(0) p, q, curr = l1, l2, l3 while p!=None and q!=None: if p.val > q.val: curr.next = q q = q.next else: curr.next = p p = p.next curr = curr.next if p != None: curr.next = p if q != None: curr.next = q return l3.next