合並單鏈表，輸出單鏈表中間元素，判斷是否有環等

1. 合並兩個有序的單鏈表成一個有序的單鏈表
方法分為遞歸實現與非遞歸實現，兩種方法都不額外開辟 內存空間

鏈表的數據結構在本博客的單鏈表逆轉，約瑟夫環等

遞歸實現：

//遞歸實現合並兩個有序單鏈表  
LinkNode* merge_list(LinkNode *pHead1, LinkNode *pHead2) 
{ 
    if(pHead1==NULL) 
        return pHead2; 
    if(pHead2==NULL) 
        return pHead1; 
    if(pHead1==NULL && pHead2==NULL) 
        return NULL; 
    LinkNode *pMergedHead=NULL; 
    if(pHead1->value<pHead2->value) 
    { 
        pMergedHead=pHead1; 
        pMergedHead->next = merge_list(pHead1->next, pHead2); 
    } 
    else  
    { 
        pMergedHead=pHead2; 
        pMergedHead->next=merge_list(pHead1, pHead2->next); 
    } 
    return pMergedHead; 
} 

//遞歸實現合並兩個有序單鏈表
LinkNode* merge_list(LinkNode *pHead1, LinkNode *pHead2)
{
 if(pHead1==NULL)
  return pHead2;
 if(pHead2==NULL)
  return pHead1;
 if(pHead1==NULL && pHead2==NULL)
  return NULL;
 LinkNode *pMergedHead=NULL;
 if(pHead1->value<pHead2->value)
 {
  pMergedHead=pHead1;
  pMergedHead->next = merge_list(pHead1->next, pHead2);
 }
 else
 {
  pMergedHead=pHead2;
  pMergedHead->next=merge_list(pHead1, pHead2->next);
 }
 return pMergedHead;
}

非遞歸實現：

//非遞歸實現合並兩個有序單鏈表(不額外開辟空間)  
LinkNode* non_merge_list(LinkNode *pHead1, LinkNode *pHead2) 
{ 
    if(pHead1==NULL) 
        return pHead2; 
    if(pHead2==NULL) 
        return pHead1; 
    if(pHead1==NULL && pHead2==NULL) 
        return NULL; 
    LinkNode *pMergedHead = NULL; 
    LinkNode *q=NULL; 
    if(pHead1->value<pHead2->value) 
    { 
        pMergedHead=pHead1; 
        pHead1=pHead1->next; 
    } 
    else 
    { 
        pMergedHead=pHead2; 
        pHead2=pHead2->next; 
    }    
    q=pMergedHead; 
    while(pHead1 && pHead2) 
    { 
        if(pHead1->value<pHead2->value) 
        { 
            q->next=pHead1; 
            pHead1=pHead1->next; 
        } 
        else 
        { 
            q->next=pHead2; 
            pHead2=pHead2->next; 
        } 
        q=q->next; 
    } 
    if(pHead1) 
    { 
        while(pHead1) 
        { 
            q->next=pHead1; 
            q=q->next; 
            pHead1=pHead1->next; 
        } 
    } 
    if(pHead2) 
    { 
        while(pHead2) 
        { 
            q->next=pHead2; 
            q=q->next; 
            pHead2=pHead2->next; 
        } 
    } 
    return pMergedHead; 
} 

//非遞歸實現合並兩個有序單鏈表(不額外開辟空間)
LinkNode* non_merge_list(LinkNode *pHead1, LinkNode *pHead2)
{
 if(pHead1==NULL)
  return pHead2;
 if(pHead2==NULL)
  return pHead1;
 if(pHead1==NULL && pHead2==NULL)
  return NULL;
 LinkNode *pMergedHead = NULL;
 LinkNode *q=NULL;
 if(pHead1->value<pHead2->value)
 {
  pMergedHead=pHead1;
  pHead1=pHead1->next;
 }
 else
 {
  pMergedHead=pHead2;
  pHead2=pHead2->next;
 } 
 q=pMergedHead;
 while(pHead1 && pHead2)
 {
  if(pHead1->value<pHead2->value)
  {
   q->next=pHead1;
   pHead1=pHead1->next;
  }
  else
  {
   q->next=pHead2;
   pHead2=pHead2->next;
  }
  q=q->next;
 }
 if(pHead1)
 {
  while(pHead1)
  {
   q->next=pHead1;
   q=q->next;
   pHead1=pHead1->next;
  }
 }
 if(pHead2)
 {
  while(pHead2)
  {
   q->next=pHead2;
   q=q->next;
   pHead2=pHead2->next;
  }
 }
 return pMergedHead;
}

 

2 輸出單鏈表中的中間元素(若鏈表節點個數為偶數，則輸出中間兩個的任意一個)

思路：利用兩個指針從頭節點開始遍歷，一個走一步，一個走兩步，當一次走兩步的指針走到鏈表末尾時，此時一次走一步的指針就指向鏈表的中間節點

代碼如下：

LinkNode* print_mid_node(LinkNode *pHead) 
{ 
    LinkNode *pOne = pHead, *pTwo = pHead; 
    while(1)     
    { 
        pOne = pOne->next; 
        pTwo = pTwo->next->next; 
        if(pTwo==NULL || pTwo->next==NULL) 
            return pOne; 
    } 
} 

LinkNode* print_mid_node(LinkNode *pHead)
{
 LinkNode *pOne = pHead, *pTwo = pHead;
 while(1) 
 {
  pOne = pOne->next;
  pTwo = pTwo->next->next;
  if(pTwo==NULL || pTwo->next==NULL)
   return pOne;
 }
}

3 判斷單戀表是否有環

思路與第二題一樣，只是結束條件不一樣，如果當一次走一步的指針等於一次走兩步的指針時，則表示該鏈表有環

代碼如下：

bool is_circle_list(LinkNode *pHead) 
{ 
    LinkNode *pOne = pHead, *pTwo = pHead; 
    while(1) 
    { 
        pOne = pOne->next; 
        pTwo = pTwo->next->next; 
        if(pOne == pTwo) 
            return true; 
        if(pTwo==NULL || pTwo->next==NULL) 
            return false; 
    } 
} 

bool is_circle_list(LinkNode *pHead)
{
 LinkNode *pOne = pHead, *pTwo = pHead;
 while(1)
 {
  pOne = pOne->next;
  pTwo = pTwo->next->next;
  if(pOne == pTwo)
   return true;
  if(pTwo==NULL || pTwo->next==NULL)
   return false;
 }
}