【Leetcode 21】合并两个有序链表

【Leetcode 21】合并两个有序链表

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; } }}

python版本

class Solution: def mergeTwoLists(self, l1, l2): if l1 is None: return l2 elif l2 is None: return l1 elif l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) # l1的值比l2小，所以l1向后移动 return l1 #返回较小的那个节点，此时，l1小就返回l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2

注意哨兵节点的使用，没有哨兵节点，代码就会复杂一点

java版本

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode prehead = new ListNode(-1); ListNode prev = prehead; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { prev.next = l1; l1 = l1.next; } else { prev.next = l2; l2 = l2.next; } prev = prev.next; } // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可 prev.next = l1 == null ? l2 : l1; return prehead.next; }}

python版本

class Solution: def mergeTwoLists(self, l1, l2): # maintain an unchanging reference to node ahead of the return node. prehead = ListNode(-1) prev = prehead while l1 and l2: if l1.val <= l2.val: prev.next = l1 l1 = l1.next else: prev.next = l2 l2 = l2.next prev = prev.next # exactly one of l1 and l2 can be non-null at this point, so connect # the non-null list to the end of the merged list. prev.next = l1 if l1 is not None else l2 return prehead.next

参考链接

与剑指offer题目相同​

​​https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。