0 引言
题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。链表结点定义如下。
struct ListNode { int val; ListNode* next; }
1 抽象问题具体化
举例1： 链表1：1->3->5->7 链表1：2->4->6->8 合并链表：1->2->3->4->5->6->7->8 举例2： 链表1：NULL 链表2：1->2->3->4 合并链表：1->2->3->4 举例3： 链表1：NULL 链表2：NULL 合并链表：NULL
2 具体问题抽象化
（1）定义接口：
ListNode* Merge(ListNode* p, ListNode* q);
（2）操作流程
1）输入两个链表，并定义合并链表头结点，保留当前比较小的链表头结点作为返回结点，合并链表的尾节点指向较小的结点
2）开始循环操作：定义循环结束条件，某个链表活动结点指向了NULL，此时跳出循环，而且合并链表尾节点将等于另一个链表活动结点。
3）循环中的操作：当前活动结点等于两个活动结点中的一个，判断两个活动结点哪个小（或者等于），合并结点尾指针指向大的那个结点，并将另一个结点向前移动一个位置。
4）返回合并链表头结点
（3）流程图
3 demo
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if(pHead1 == NULL) return pHead2; if(pHead2 == NULL) return pHead1; ListNode* r = NULL; if(pHead1->val <= pHead2->val) r = pHead1; else r = pHead2; ListNode* tail = r; // 合并链表活动尾节点 while(!(pHead1 == NULL || pHead2 == NULL)){ ListNode* next; if(pHead1->val <= pHead2->val){ next = pHead1->next; tail->next = pHead2; pHead1 = next; tail = tail -> next; } else{ next = pHead2->next; tail->next = pHead1; pHead2 = next; tail = tail -> next; } } return r; }
4 代码优化
（1）分析：上述代码中合并列表的尾结点tail与两个活动结点中的一个相等，导致在延长合并链表时（tail->next = pHead2），出现了断裂，不得不保存next，增加了内存开支。可以通过优化代码避免这一点。写法如下。
ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ if(pHead1 == NULL) return pHead2; if(pHead2 == NULL) return pHead1; ListNode* r = NULL; if(pHead1->val <= pHead2->val){ r = pHead1; pHead1 = pHead1->next; // 改动1 } else{ r = pHead2; pHead2 = pHead2->next; // 改动2 } ListNode* tail = r; // 合并链表活动尾节点 while(!(pHead1 == NULL || pHead2 == NULL)){
// ListNode* next; // 改动3 if(pHead1->val <= pHead2->val){ tail->next = pHead1; pHead1 = pHead1->next; // 改动4 tail = tail -> next; } else{ tail->next = pHead2; pHead2 = pHead2->next; // 改动5 tail = tail -> next; } } tail ->next = pHead1?pHead1:pHead2; // 改动6 return r; }