LeetCode Notes_#21 Merge Two Sorted Lists(剑指Offer#25)

LeetCode Notes_#21 Merge Two Sorted Lists(剑指Offer#25)

LeetCode剑指offer

Contents

• • 题目
  • 思路和解答
    • 思路
    • python解答
    • Java解答

题目

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4

Output: 1->1->2->3->4->4

感觉他的题目过于简单，有一些会模糊的地方没有讲清楚

1. 输入是包含长度不同的情况的，这个要考虑；最后剩下的那一部分，直接连在最后
2. 最后输出的整个链表也必须是顺序的（由小到大）

思路和解答

思路

思路其实跟之前的2.Add Two Numbers类似，操作链表的套路都是这样.但是不能完全抄过来，考虑一下特殊的部分

python解答

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummyHead=ListNode(0)
        p=l1
        q=l2#两个链表的长度不同怎么办？
        tmpNode=dummyHead
        
        while(p!=None and q!=None):
            a=p.val 
            b=q.val 
            if a>=b:
                tmpNode.next=ListNode(b)
                q=q.next
            else:
                tmpNode.next=ListNode(a)
                p=p.next
            tmpNode=tmpNode.next   
            
        tmpNode.next=p if p!=None else q    
        
        return dummyHead.next

Java解答

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode head = dummyHead;
        while(l1 != null && l2 != null){//遇到其中一个遍历完成，结束循环
            if(l1.val <= l2.val){
                head.next = l1;
                head = head.next;//这句其实可以写到条件判断之外
                l1 = l1.next;
            }else{
                head.next = l2;
                head = head.next;
                l2 = l2.next;
            }
        }
    //一个链表遍历完了，那就把另一个链表接到当前结果的最后
        if(l1 != null) head.next = l1;
        if(l2 != null) head.next = l2;
        return dummyHead.next;
    }
}