01、题目分析
示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 首先我们拿到题目乍眼一看,类似这种链表的合并问题。基本上马上可以想到需要设置一个哨兵节点,这可以在最后让我们比较容易地返回合并后的链表。(不懂哨兵节点的同学,可以先移驾到 哨兵节点:删除链表倒数第N个节点 进行学习) 假设我们的链表分别为: l1 = [1,2,4] l2 = [1,3,4] 同时我们设定一个 “prehead” 的哨兵节点,大概是下面这样: 02、题目图解如上图所示,首先我们维护一个 prehead 的哨兵节点。我们其实只需要调整它的 next 指针。让它总是指向l1或者l2中较小的一个,直到l1或者l2任一指向null。这样到了最后,如果l1还是l2中任意一方还有余下元素没有用到,那余下的这些元素一定大于prehead已经合并完的链表(因为是有序链表)。我们只需要将这些元素全部追加到prehead合并完的链表后,最终就得到了我们需要的链表。大概流程如下:
03、Go语言示例根据以上分析,我们可以得到下面的题解: func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { prehead := &ListNode{} result := prehead for l1 != nil && l2 != nil { if l1.Val < l2.Val { prehead.Next = l1 l1 = l1.Next }else{ prehead.Next = l2 l2 = l2.Next } prehead = prehead.Next } if l1 != nil { prehead.Next = l1 } if l2 != nil { prehead.Next = l2 } return result.Next } java: class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(); ListNode result = prehead; while (l1 != null && l2 != null) { if (l1.val < l2.val) { prehead.next = l1; l1 = l1.next; }else{ prehead.next = l2; l2 = l2.next; } prehead = prehead.next; } if (l1 != null) { prehead.next = l1; } if (l2 != null) { prehead.next = l2; } return result.next; } } 我把我写的所有题解都整理成了一本电子书,每道题都配有完整图解。点击即可下载
|
|