聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

一道腾讯面试题,击败100%的用户,合并排序链表

2022-01-19 10:46 浏览: 1819 次 我要评论(0 条) 字号:

来自公众号:小夕学算法

题目

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 限制:

0 <= 链表长度 <= 1000

注意:本题与主站 21 题相同:https://leetcode-cn.com/problems/merge-two-sorted-lists/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

文字思路

  • 设置dummy为哑结点,放置于新链表之前,最后返回的就是dummy.next;设置cur为当前节点,从dummy开始
  • 当两个链表都非空时进入循环,令新链表的下一个节点cur.next为val更小的节点,相应的链表节点后移一位
  • 每次循环记得cur也要后移一位
  • 如果循环结束后还有链表非空,cur指向非空链表
  • 返回dummy.next

图解思路

上述图片中的文字:

  • 创建一个伪头结点 tempHead 节点 cur 指向 tempHead 节点 接下来比较 head1 和 head2 两个链表 哪个节点小 就把 tempHead 指向谁
  • head1.val >= head2.val 所以 head2 节点是值较小的,让cur.next指向head2节点
  • cur.next指向了head2,如图所示,接着让head2 = head2.next,让head2 继续参与接下来的比较。
  • 完成了cur.next 指向了head2,head2 = head2.next,接下来让 cur指向下一个节点 cur = cur.next
  • 完成了cur.next指向了head2,head2 = head2.next,cur = cur.next变成了如图所示。
  • 接着继续重复上述过程 继续比较 head1.val < head2.val
  • 由于 head1.val < head2.val 继续执行之前的三步:cur.next = head1 head1 = head1.next cur = cur.next
  • 由于 head1.val < head2.val 继续执行之前的三步:cur.next = head1 head1 = head1.next cur = cur.next 执行完这三步以后,如图所示。
  • 接下来继续比较head1.val和head2.val 因为 head1.val < head2.val 继续执行之前的三步:cur.next = head1 head1 = head1.next cur = cur.next
  • cur.next = head1 head1 = head1.next cur = cur.next如图所示
  • 接下来继续比较head1.val和 head2.val 因为 head1.val > head2.val:所以执行 cur.next = head2 head2 = head2.next cur = cur.next
  • 接下来继续比较head1.val和 head2.val 因为 head1.val >= head2.val:所以继续执行 cur.next = head2 head2 = head2.next cur = cur.next
  • 执行完如图所示,head1指向了null,所以排序列表一遍历结束了,所以把排序列表二接到合并排序列表后面。
  • 接到后面,cur.next = head2 完成全部排序。
  • 由于需要返回1-1-2-3-4-4 所以最后返回tempHead.next 节点

动画

--- EOF ---


推荐↓↓↓


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复