描述
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.
分析
合并两个有序的链表。分别采用递归和遍历的方式。
解决方案1(Python)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
class Solution(object): def mergeTwoLists(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ if l1 == None: return l2 if l2 == None: return l1 if l1.val <= l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 l2.next = self.mergeTwoLists(l1, l2.next) return l2
|
解决方案2(C++)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
|
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head; if(l1 == NULL) return l2; if(l2 == NULL) return l1; if(l1->val <= l2->val) { head = l1; l1 = l1->next; }else { head = l2; l2 = l2->next; } ListNode* head_back = head; while(l1 != NULL && l2 != NULL) { if(l1->val <= l2->val) { head->next = l1; l1 = l1->next; }else { head->next = l2; l2 = l2->next; } head->next->next = NULL; head = head->next; } if(l1) { head->next = l1; } if(l2) { head->next = l2; } return head_back; } };
|
解决方案3(Java)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
public 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; } l2.next = mergeTwoLists(l1, l2.next); return l2; } }
|
解决方案4(Golang)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { if l1 == nil { return l2 } if l2 == nil { return l1 } var result *ListNode if l1.Val >= l2.Val { result = l2 result.Next = mergeTwoLists(l1, l2.Next) } else { result = l1 result.Next = mergeTwoLists(l1.Next, l2) } return result }
|
相关问题