当前位置:首页>维修大全>综合>

链表合并的算法原理

链表合并的算法原理

更新时间:2025-07-25 17:16:26

链表合并的算法原理

链表合并是指将两个有序链表合并成一个有序链表的过程,算法的原理是比较两个链表的头节点,将较小的节点作为新链表的头节点,然后继续比较两个链表的头节点,将较小的节点接到新链表的尾部,直到其中一个链表为空,将另一个链表剩下的节点接到新链表的尾部即可。这个过程需要维护三个指针,分别指向新链表、链表1、链表2的当前节点,时间复杂度为O(m+n)。

申请两个新指针,h3和h3_head,h3_head指向新链表的头结点,h3指向新链表,并可以向后移动位置。

如果 h1.val <= h2.val,则h3.next = h1; h1 = h1.next; h3 = h3.next。反之亦然。

当h1或者h2其中一个链表遍历结束后,h3指向另一个链表h1或者h2剩下的部分。

更多栏目