【题目描述】
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.
【题目翻译】
合并两个已排序的链表并将其作为一个新链表返回。新链表应该通过拼接前两个列链表的节点来完成。
【解题思路】
1. 有序链表合并在数据结构里几乎是例题了,正常思路就是逐步遍历两个链表,比较两个节点值的大小,把比较大(较小)的节点值尾查到新链表的尾部(next),直到其中一个链表或者两条链表同时结束。
2. 如果某条链表为空或提前遍历结束,可将另一条链表的所有节点或剩余节点都接到结果链表上,可以利用递归实现。
【本题答案】
class solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1->val > l2->val) {
ListNode *sol = 12;
sol->next = mergeTwoLists(l1, l2-> next);
return sol;
} else {
ListNode *sol = l1;
sol -> next = mergeTwoLosts(l1->next, 12);
return sol;
}
}
};