本文共 1402 字，大约阅读时间需要 4 分钟。

解法1：迭代

注意：

​ ●要考虑输入为空的情况。

​ ●要注意返回和遍历，用一个哨兵节点来返回，用一个cur指针来遍历

​ ●注意每轮要更新cur即cur = cur->next;

代码：

class Solution {   public:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {           //考虑输入为空        if(l1 == NULL && l2 == NULL)            return NULL;        if(l1 == NULL)            return l2;        if(l2 == NULL)            return l1;        //要新建一个哨兵节点，利用哨兵节点的next来返回head        ListNode* dummynode = new ListNode;        //利用一个指针来遍历        ListNode* cur = dummynode;        while(l1 != NULL && l2 != NULL){               if(l1->val <= l2->val){                   cur->next = l1;                l1 = l1->next;            }            else{                   cur->next = l2;                l2 = l2->next;            }            cur = cur->next;        }        //至少有一个为空        if(l1 != NULL)            cur->next = l1;        if(l2 != NULL)            cur->next = l2;        return dummynode->next;    }};

解法2：递归

注意：

●通过l1和l2来返回最后的头节点

代码：

class Solution {   public:    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {           if(l1 == NULL && l2 == NULL)            return NULL;        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;        }    }};