这道题的要求是合并两个有序单链表。
描述很简单，思路更加简单，就是先创建一个新的链表节点，然后用两个指针指向这两个单链表，比较这两个指针指向元素的大小，将较小的一个的值赋给新节点的元素，如果这两个元素相同，那随便赋谁的值都可以。当这两个链表有一个已经遍历完之后，就直接把另一条链表的其余元素复制到新链表中去。
代码如下：
|
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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == NULL && l2 == NULL) { return NULL; } else if (! l1 && l2) { return l2; } else if (l1 && !l2) { return l1; } else { ListNode *ptrToA = l1, *ptrToB = l2; ListNode *cur = (ListNode *)malloc(sizeof(ListNode)); ListNode *head = cur; while(ptrToA && ptrToB) { while(ptrToA && ptrToB && (ptrToA->val < ptrToB->val)) { ListNode *newCell = (ListNode *)malloc(sizeof(ListNode)); newCell->val = ptrToA->val; cur->next = newCell; cur = newCell; ptrToA = ptrToA->next; } while(ptrToA && ptrToB && (ptrToA->val > ptrToB->val)) { ListNode *newCell = (ListNode *)malloc(sizeof(ListNode)); newCell->val = ptrToB->val; cur->next = newCell; cur = newCell; ptrToB = ptrToB->next; } while(ptrToA && ptrToB && (ptrToA->val == ptrToB->val)) { ListNode *newCellA = (ListNode *)malloc(sizeof(ListNode)); newCellA->val = ptrToA->val; cur->next = newCellA; cur = newCellA; ListNode *newCellB = (ListNode *)malloc(sizeof(ListNode)); newCellB->val = ptrToB->val; cur->next = newCellB; cur = newCellB; ptrToA = ptrToA->next; ptrToB = ptrToB->next; } } if(!ptrToA && ptrToB) { while(ptrToB) { ListNode *newCell = (ListNode *)malloc(sizeof(ListNode)); newCell->val = ptrToB->val; cur->next = newCell; cur = newCell; ptrToB = ptrToB->next; } cur->next = NULL; } else if(ptrToA && !ptrToB) { while(ptrToA) { ListNode *newCell = (ListNode *)malloc(sizeof(ListNode)); newCell->val = ptrToA->val; cur->next = newCell; cur = newCell; ptrToA = ptrToA->next; } cur->next = NULL; } else if (!ptrToA && !ptrToB ) { cur->next = NULL; } return head->next; } } }; |
Update: 今天从剑指offer 上看到了这道题的递归解法，相比于上面的方法，递归解法显得更加优美简单。代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { if (l1 == NULL) { return l2; } else if (l2 == NULL) { 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; } } }; |