我的题解

  最开始，我的思路是最简单的思路，就是再新申请空间，遍历两个链表。最后拼装成结果。

class Solution {
	public:
		ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
			ListNode dummy(0);
			ListNode* rp = &dummy;
			while(l1!=NULL&&l2!=NULL) {
				int val1 = l1->val;
				int val2 = l2->val;
				int val = val2;
				if(val1<=val2) {
					val = val1;
					l1 = l1->next;
				} else {
					l2 = l2->next;
				}
				ListNode* np = new ListNode(val);
				rp->next = np;
				rp=np;
			}
			while(l1!=NULL) {
				ListNode* np = new ListNode(l1->val);
				rp->next = np;
				rp=np;
				l1=l1->next;
			}
			while(l2!=NULL) {
				ListNode* np = new ListNode(l2->val);
				rp->next = np;
				rp=np;
				l2=l2->next;
			}
			return dummy.next;
		}
};

  看到打败的人数很低，我稍作思考，我认为可以借助其中一个链表来做这件事，但是时间消耗还是不理想。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
			if(l1==NULL&&l2==NULL) {
				return l1;
			}
			if(l1==NULL) {
				return l2;
			}
			if(l2==NULL) {
				return l1;
			}
			ListNode* head = l1;
			
			ListNode* otherList = l2;
			ListNode* last = new ListNode(0);
			ListNode* resultDummyNode = last;
			
			if(l1->val>l2->val){
				head = l2;
				otherList = l1;
			}
			last->next = head;

			while(otherList!=NULL&&head!=NULL) {
				while(head!=NULL&&head->val<otherList->val) {
					last = head;
					head=head->next;
				}
				if(head!=NULL) {
					last->next = new ListNode(otherList->val,head);
					last = last->next;
					otherList= otherList->next;
				}
			}
			while(otherList!=NULL) {
				last->next = new ListNode(otherList->val);
				otherList = otherList->next;
				last = last->next;
			}
			return resultDummyNode->next;
    }
};

官方题解

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

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。