链表3

比眉伴天荒 2022-05-24 23:59 64阅读 0赞

1、合并链表

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

2、解答： 由于两个链表是有序的，所以就比较好解决

3、C++代码

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if(l1 == NULL) 
                return l2;
            
            if(l2 == NULL)
                return l1;
            
            ListNode *head = NULL;
            
            if(l1->val < l2->val){
                head = l1;
                l1 = l1->next;
                
            }else{
                head = l2;
                l2 = l2->next;
            }
                
            
            ListNode *p = head;        // 新建个p结点，容易多了
            
            while(l1&&l2){
                if(l1->val < l2->val){
                    p->next = l1;
                    l1 = l1->next;
                }else{
                    p->next = l2;
                    l2 = l2->next;
                }
                p = p->next;            //这句不要忘记写了
            }
            
          if(l1){               //l1 不为空的时候
              p->next = l1;
          }else{                //l1 为空
              p->next = l2;
          }
            
         return head;
        }
    };

python代码

class Solution:
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """  
            if not l1:
                return l2
            if not l2:
                return l1
            
            if l1.val < l2.val:
                head = l1
                l1 = l1.next
            else:
                head = l2
                l2 = l2.next
            
            p = head
            
            while l1 and l2:
                if(l1.val < l2.val):
                    p.next = l1
                    l1 = l1.next
                else:
                    p.next = l2
                    l2 = l2.next
                p = p.next
            
            if(l1):
                p.next = l1
            else:
                p.next = l2
                
            return head

递归解决更简单

class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if(l1==NULL) return l2;
            if(l2==NULL) return l1;
            
            if(l1->val<l2->val)
            {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
            }
            else 
            {
                l2->next =  mergeTwoLists(l1, l2->next);
                return l2;
            }