Leetcodes Solutions 21 Merge Two Sorted Lists

zhuanlan.zhihu.com

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.

Example:

Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4

思路1

利用遞歸

/** * 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(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; } }};

思路2

創建一個節點tail指針來存放兩個節點中較小的那個

class Solution{public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2){ ListNode dummy(INT_MIN); ListNode *tail = &dummy; while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next; }else{ tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; }};

推薦閱讀：