两个指针的做法，但比起2个数组有序的数组的话，链表做更容易，因为当一个链表遍历结束后，tail指针并不需要遍历另一个链表，只要直接指向它就行
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) { struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *tail = head; while(l1&&l2){ if(l1->val<l2->val){ tail->next = l1; l1 = l1->next; }else { tail->next = l2; l2 = l2->next; } tail = tail->next; } //很傻比的后面全部遍历一遍 while(l1){ tail->next = l1; l1 = l1->next; tail = tail->next; } while(l2){ tail->next = l2; l2 = l2->next; tail = tail->next; } return head->next; }
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) { struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode)); struct ListNode *tail = head; while(l1&&l2){ if(l1->val<l2->val){ tail->next = l1; l1 = l1->next; }else { tail->next = l2; l2 = l2->next; } tail = tail->next; } if(!l1)tail->next = l2; else if(!l2) tail->next = l1; return head->next; }
原文：http://www.cnblogs.com/llei1573/p/4335972.html