链表问题_合并两个排序链表

╰+哭是因爲堅強的太久メ 2022-05-21 01:57 198阅读 0赞

题目：输入两个递增排序的链表，合并这两个排序链表，使得合并之后的链表仍然使递增排序的。  
分析：即是归并排序中的归并操作，有两种具体的实现：1、使用递归的方法，2、迭代版本，逐个合并链表。实现如下：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
                val(x), next(NULL) {
        }
    };*/
    
    /*递归版本*/
      ListNode*merge(ListNode*phead1, ListNode*phead2)
      {
          if (phead1 == NULL)
              return phead2;
          else if (phead2 == NULL)
              return phead1;
    
          ListNode*pmergehead = NULL;
          if (phead1->val < phead2->val)
          {
              pmergehead = phead1;
              pmergehead->next=merge(phead1->next, phead2);
          }
          else
          {
              pmergehead = phead2;
              pmergehead->next=merge(phead1, phead2->next);
          }
         return pmergehead ;
      }
    
    /*迭代版本*/
    ListNode*Merge(ListNode*phead1, ListNode*phead2)
      {
          if (phead1 == NULL)
              return phead2;
          else if (phead2 == NULL)
              return phead1;
    
          ListNode* pnode1 = phead1;
          ListNode* pnode2 = phead2;
          ListNode* pmergehead = NULL;
    
          if (phead1->val < phead2->val)
          {
              pnode1 = pnode1->next;
              pmergehead = phead1;
          }
          else
          {
              pnode1 = pnode1->next;
              pmergehead = phead1;
          }
          ListNode*pnode3 = pmergehead;
          while (pnode1&&pnode2)
          {
              if (pnode1->val < pnode2->val)
              {
                  pnode3->next = pnode1;
                  pnode3 = pnode3->next;
                  pnode1 = pnode1->next;
              }
              else
              {
                  pnode3->next = pnode2;
                  pnode3 = pnode3->next;
                  pnode2 = pnode2->next;
              }
          }
    
          while (pnode1)
          {
              pnode3->next = pnode1;
              pnode3 = pnode3->next;
              pnode1 = pnode1->next;
          }
    
          while (pnode2)
          {
              pnode3->next = pnode2;
              pnode3 = pnode3->next;
              pnode2 = pnode2->next;
          }
          return pmergehead;
      }