
链表合并是指将两个有序链表合并成一个有序链表的过程,算法的原理是比较两个链表的头节点,将较小的节点作为新链表的头节点,然后继续比较两个链表的头节点,将较小的节点接到新链表的尾部,直到其中一个链表为空,将另一个链表剩下的节点接到新链表的尾部即可。这个过程需要维护三个指针,分别指向新链表、链表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剩下的部分。