面试题17：合并两个排序的链表

注意某个链表为null的情况，合并链表会改变原链表结构

递归：

 1 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 2 {
 3     if(pHead1 == NULL)
 4         return pHead2;
 5     else if(pHead2 == NULL)
 6         return pHead1;
 7 
 8     ListNode* pMergedHead = NULL;
 9 
10     if(pHead1->m_nValue < pHead2->m_nValue)
11     {
12         pMergedHead = pHead1;
13         pMergedHead->m_pNext = Merge(pHead1->m_pNext, pHead2);
14     }
15     else
16     {
17         pMergedHead = pHead2;
18         pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);
19     }
20 
21     return pMergedHead;
22 }

自己写的非递归：

先找到头结点，然后用head3遍历修改链表12每个节点的指向

 1 ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 2 {
 3     if (pHead1 == NULL)
 4         return pHead2;
 5     if (pHead2 == NULL)
 6         return pHead1;
 7     ListNode *pMergeHead = NULL;
 8     if (pHead1->m_nValue < pHead2->m_nValue)
 9     {
10         pMergeHead = pHead1;
11         pHead1 = pHead1->m_pNext;
12     }
13     else
14     {
15         pMergeHead = pHead2;
16         pHead2 = pHead2->m_pNext;
17     }
18     ListNode *pHead3 = pMergeHead;
19     while (pHead1 != NULL && pHead2 != NULL)
20     {
21         if (pHead1->m_nValue < pHead2->m_nValue)
22         {
23             pHead3->m_pNext = pHead1;
24             pHead3 = pHead3->m_pNext;
25             pHead1 = pHead1->m_pNext;
26         }
27         else
28         {
29             pHead3->m_pNext = pHead2;
30             pHead3 = pHead3->m_pNext;
31             pHead2 = pHead2->m_pNext;
32         }
33     }
34     if (pHead1 == NULL)
35         pHead3->m_pNext = pHead2;
36     else
37         pHead3->m_pNext = pHead1;
38 
39     return pMergeHead;
40 }