Merge Two Sorted Lists
前言:
这是归并排序的其中一个步骤,如果大家对数据结构知识点内容掌握比较到位的话,非常简单。
文字思想:
当两个单链表都不为空的时候,持续遍历两个单链表。将两个链表中更小的结点追加到新的单链表的尾巴上,并且对应的链表后移。
直到其中一个链表为空,再将不空的链表追加到新链表后面。
例子:
链表一:1, 2, 4,
链表二:1, 3, 4, 7, 8, 10,
新链表:
当前l1处理元素:1
当前l2处理元素:1
当前l1处理元素更小,尾插到新链表
l1后移一位
链表一:2, 4,
链表二:1, 3, 4, 7, 8, 10,
新链表:1,
当前l1处理元素:2
当前l2处理元素:1
当前l2处理元素更小,尾插到新链表
l2后移一位
链表一:2, 4,
链表二:3, 4, 7, 8, 10,
新链表:1, 1,
当前l1处理元素:2
当前l2处理元素:3
当前l1处理元素更小,尾插到新链表
l1后移一位
链表一:4,
链表二:3, 4, 7, 8, 10,
新链表:1, 1, 2,
当前l1处理元素:4
当前l2处理元素:3
当前l2处理元素更小,尾插到新链表
l2后移一位
链表一:4,
链表二:4, 7, 8, 10,
新链表:1, 1, 2, 3,
当前l1处理元素:4
当前l2处理元素:4
当前l1处理元素更小,尾插到新链表
l1后移一位
链表一:
链表二:4, 7, 8, 10,
新链表:1, 1, 2, 3, 4,
l1为空,现在直接将l2追加到新链表的尾巴
1, 1, 2, 3, 4, 4, 7, 8, 10,
代码:
复杂度:
时间复杂度:O(n+m),因为在循环的时候每次处理一个元素。
空间复杂度:O(1)。
积累:
整体。
领取专属 10元无门槛券
私享最新 技术干货