/

// 7. 题目17 合并两个排序链表

//时间复杂度：O(n), 空间复杂度：O(1)

ListNode
     
      * MergeSortedLists(ListNode
      
       * plhsHead, ListNode
       
        * prhsHead){    if (NULL == plhsHead)    {        return prhsHead;    }    if (NULL == prhsHead)    {        return plhsHead;    }    ListNode
        
         * pMergeHead = NULL;    if (plhsHead->m_stData < prhsHead->m_stData)    {        pMergeHead = plhsHead;        pMergeHead->m_pNextNode = MergeSortedLists(plhsHead->m_pNextNode, prhsHead);    }    else    {        pMergeHead = prhsHead;        pMergeHead->m_pNextNode = MergeSortedLists(plhsHead, prhsHead->m_pNextNode);    }    return pMergeHead;}// 非递归方法：合并两个有序链表//时间复杂度：O(n), 时间复杂度(1)ListNode
         
          * MergeSortedLists_1(ListNode
          
           * pHead1, ListNode
           
            * pHead2){ if (NULL == pHead1) { return pHead2; } if (NULL == pHead2) { return pHead1; } // 1.新链表头结点 ListNode
            
             * pMergeHead = NULL; if (pHead1->m_stData <= pHead2->m_stData) { pMergeHead = pHead1; pHead1 = pHead1->m_pNextNode; } else { pMergeHead = pHead2; pHead2 = pHead2->m_pNextNode; } ListNode
             
              * pTmpNode = pMergeHead; // 2.比较两个链表，较小的节点加入新链表后面 while (pHead1 && pHead2) { if (pHead1->m_stData <= pHead2->m_stData) { pTmpNode = pHead1; pHead1 = pHead1->m_pNextNode; } else { pTmpNode = pHead2; pHead2 = pHead2->m_pNextNode; } // 不能让新链表中断！！！！ if (NULL != pTmpNode->m_pNextNode) { pTmpNode = pTmpNode->m_pNextNode; } } // 3.链接剩余的元素 if (pHead1 && pTmpNode) { pTmpNode->m_pNextNode = pHead1; } if (pHead2 && pTmpNode) { pTmpNode->m_pNextNode = pHead2; } return pMergeHead;}void MergeSortedListsTestFunc(){ cout << "\n\n --------------- MergeSortedListsTestFunc Start -------------->" << endl; // 初始化链表1 int aiArray[] = { 1, 2, 3, 4, 5, 6, 7, 8}; int iLen = sizeof(aiArray) / sizeof(int); TRAVERSAL_ARRAY(aiArray, iLen); CSingleList
              
               * pList = new CSingleList
               
                (); if (!pList) { return; } for (int i = 0; i < iLen; i++) { pList->Insert(aiArray[i]); } pList->Traversal(); // 初始化链表2 int aiArray2[] = { 9, 10, 11, 12, 13, 14, 15}; int iLen2 = sizeof(aiArray2) / sizeof(int); TRAVERSAL_ARRAY(aiArray2, iLen2); CSingleList
                
                 * pList2 = new CSingleList
                 
                  (); if (!pList2) { SAVE_DELETE(pList); return; } for (int i = 0; i < iLen2; i++) { pList2->Insert(aiArray2[i]); } pList2->Traversal(); ListNode
                  
                   * pHead1 = pList->GetHeadNode(); ListNode
                   
                    * pHead2 = pList2->GetHeadNode(); // 合并链表 //ListNode
                    
                     * pMergeNode = MergeSortedLists(pHead1, pHead2); //if (pMergeNode) //{ // cout << "两个有序链表合并后: " << endl; // TraversalList(pMergeNode); //} //cout << "合并后原来链表值: " << endl; //pList->Traversal(); //pList2->Traversal(); ListNode
                     
                      * pMergeNode = MergeSortedLists_1(pHead1, pHead2); if (pMergeNode) { cout << "两个有序链表合并后: " << endl; TraversalList(pMergeNode); } // 释放内存 SAVE_DELETE(pList); // list 与 pList2 已经合并在一起，不用重复释放pLIst2!!!! //SAVE_DELETE(pList2); cout << "\n\n --------------- MergeSortedListsTestFunc End -------------->" << endl;}