剑指offer-合并两个排序的链表

问题

题目：[合并两个排序的链表]

思路

传统merge的思路不说了，因为此时空间的复杂度是O(N). 主要说就地合并的思路。当然，这个题其实牛客的测试用例有问题，考虑不全面。 基本思想就是当p的当前值比q的当前值小的时候，q的上一个元素要指向p。当然，这有个前提是q的上一个元素不能指向pre_p，否则没有没有指向的意义。比如 1->3->5, 2->100->101。牛客没有考虑这种测试用例

代码

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* p = pHead1; ListNode* q = pHead2; if(!p && !q) return NULL; if(p && !q) return p; if(!p && q) return q; ListNode* p_pre = NULL; ListNode* q_pre = NULL; while(p&&q){ if( p->val < q->val ){ if(q_pre && q_pre->next != p_pre ){ q_pre->next = p; } p_pre = p; p = p->next; } else{ if(p_pre && p_pre->next != q_pre ){ p_pre->next = q; } q_pre = q; q = q->next; } } if(p) q_pre->next = p; if(q) p_pre->next = q; if(pHead1->next == pHead2) return pHead1; else return pHead2; } };