Leetcode004:合并两个有序链表

题解

第一种解法:递归

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val<list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2

时间和内存：

时间复杂度：O(n+m)
空间复杂度：O(n+m）

第二种解法:迭代

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prehead = ListNode(-1)
        prev = prehead
        
        while list1 and list2:
            if list1.val<=list2.val:
                prev.next = list1
                list1 =list1.next
            else:
                prev.next = list2
                list2 =list2.next
            prev=prev.next
        
        prev.next = list1 if list1 is not None else list2
        
        return prehead.next

图解：

时间和内存：

时间复杂度：O(n+m)
空间复杂度：O(1）

JS解法

function Merge(pHead1, pHead2)
{
    // write code here
    //比较两个链表的首结点，哪个小的的结点则合并到第三个链表尾结点，并向前移动一个结点。
    ==//1.递归思路
//     if(!pHead1) return pHead2
//     if(!pHead2) return pHead1
//     if(pHead1.val<=pHead2.val){
//         pHead1.next=Merge(pHead1.next,pHead2)//比较大小插入小的
//         return pHead1
//     }
//     else{
//         pHead2.next=Merge(pHead1,pHead2.next)
//         return pHead2
//     }
    //2.迭代思路
    //再生成一个列表，存数据
    let prehead = {};
    let prev = prehead
    
    if(!pHead1) {
         prev.next=pHead2
     }
    else{
        prev.next=pHead1
    }
    
    while(pHead1&&pHead2){
        if(pHead1.val<=pHead2.val){
            prev.next=pHead1
            pHead1=pHead1.next//往后移一个
        }
        else{
            prev.next=pHead2
            pHead2=pHead2.next
        }
         prev=prev.next //往后移
    } 
     prev.next = pHead1 ? pHead1 : pHead2 //将剩余的合并
        return prehead.next
     
}

生成新的node
const prev=new ListNode（-1）一直在报错
所以直接用一个列表存