leetcode 21 Merge Two Sorted Lists

 

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.

 

我的解决方式：

 

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution { public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(NULL==l1) return l2;if(NULL==l2) return l1;ListNode* head = NULL;if(l1->val < l2->val) {head = l1; l1 = l1->next; }else { head = l2; l2 = l2->next;}ListNode* p = head; // pointer to form new listwhile(l1!=NULL&&l2!=NULL){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;} };

 

递归c++解法：

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(l2->next, l1);return l2;}} };

 

 

python递归解决方式：

 

def mergeTwoLists(self, l1, l2):if not l1:return l2elif not l2:return l1else:if l1.val <= l2.val:l1.next = self.mergeTwoLists(l1.next, l2)return l1else:l2.next = self.mergeTwoLists(l1, l2.next)return l2

 

 

python非递归：

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = Noneclass Solution:# @param {ListNode} l1# @param {ListNode} l2# @return {ListNode}def mergeTwoLists(self, l1, l2):p1 = l1p2 = l2guard = ListNode(0)q = guardwhile p1 is not None and p2 is not None:if p1.val <= p2.val:q.next = p1p1 = p1.nextq = q.nextelse:q.next = p2p2 = p2.nextq = q.nextif p1 is not None:q.next = p1if p2 is not None:q.next = p2return guard.next

 

python递归解决方式2：

If both lists are non-empty, I first make sure a starts smaller, use its head as result, and merge the remainders behind it. Otherwise, i.e., if one or both are empty, I just return what's there.class Solution:def mergeTwoLists(self, a, b):if a and b:if a.val > b.val:a, b = b, aa.next = self.mergeTwoLists(a.next, b)return a or b

 

转载于:https://www.cnblogs.com/mfrbuaa/p/5371604.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的leetcode 21 Merge Two Sorted Lists的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。