一道编程题——合成有序链表

题目描述与分析

将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。

这一题和反转链表一样，属于链表的基础操作之一。

同样有递归和迭代两种方式实现。

代码实现

递归

首先找出两个链表（链表1和链表2）头节点中较小的一个（假设为链表1），作为新链表的头节点，然后递归链表1头节点的后一个节点和链表2.

python实现

# 递归
class Solution:
    def mergeTwoLists(self , l1 , l2 ):
        # write code here
        # 存在空链表，直接返回另一个
        if(not l1 or not l2):
            root = l1 if not l2 else l2
            return root
        # 链表1小，递归链表1后一个节点和链表2.
        if(l1.val <= l2.val):
            root = l1
            root.next = self.mergeTwoLists(l1.next, l2)
        # 反之，递归链表1和链表2的后一个节点
        else:
            root = l2
            root.next = self.mergeTwoLists(l1, l2.next)
        return root

C++实现

// 递归
class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        ListNode* root;
        // 存在空链表，则返回另一个链表
        if(l1 == NULL or l2 == NULL){
            root = (l1 == NULL) ? l2 : l1; 
            return root;
        } 
        // l1小，则新节点为l1，并递归l1的下一个节点和l2
        if(l1-> val <= l2->val){
            root = l1;
            root->next = mergeTwoLists(l1->next, l2);
        }
        // l2小，则新节点为l2，并递归l1和l2的下一个节点
        else{
            root = l2;
            root->next = mergeTwoLists(l1, l2->next);
        }
        return root;
    }
};

迭代

依次遍历两个链表，小的加入到新链表。

python实现

# 迭代
class Solution:
    def mergeTwoLists(self , l1 , l2 ):
        # write code here
        # 存在空链表
        if(not l1 or not l2):
            root = l1 if not l2 else l2
            return root
        
        # 设置root指针指向l1,l2中较小的节点
        if l1.val<=l2.val:
            a, b = l1.next, l2
            root = l1
        else:
            a, b = l1, l2.next
            root = l2

        curr = root
        # 遍历节点，小的加到新链表后面
        while(a and b):
            if a.val<=b.val:
                curr.next = a
                
                a = a.next
            else:
                curr.next = b
                b = b.next
            curr = curr.next
        # 没有遍历完的链表直接接到后面
        curr.next = a if a else b
        return root

C++实现

// 迭代
class Solution {
public:
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // write code here
        ListNode* root;
        // 存在空链表，则返回另一个链表
        if(l1 == NULL or l2 == NULL){
            root = (l1 == NULL) ? l2 : l1; 
            return root;
        } 
        // 新链表的头节点指向两个链表中较小的一个
        if(l1->val <= l2->val){
            root = l1;
            l1 = l1->next;
        }
        else{
            root = l2;
            l2 = l2->next;
        }
        // 迭代，依次比较剩余两个链表的头节点大小，小的加入到新链表
        ListNode *tmp = root;
        while(l1!=NULL && l2!=NULL){
            if(l1->val <= l2->val){
                tmp->next = l1;
                l1 = l1->next;
            }
            else{
                tmp->next = l2;
                l2 = l2->next;
            }
            tmp = tmp->next;
        }
        // 其中一个链表迭代结束，则另一个的剩余部分直接接到后面
        tmp->next = (l1!=NULL) ? l1 : l2;
        return root;
    }
};