合并排序链表

1.迭代实现

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
      auto res=pHead1;
      ListNode* pre=0;
      auto h1=pHead1,h2=pHead2;
      for(;h1&&h2;)
      {
        if(h1->val>=h2->val)
        {
          if(pre==0)
          { auto temp=h2->next;
            h2->next=h1;
            pre=h2;
            res=h2;
            h2=temp;
          }
          else
          {
            auto temp=h2->next;
            pre->next=h2;
            h2->next=h1;
            pre=h2;
            h2=temp;
          }

        }
        else
        {
          pre=h1;
          h1=h1->next;
        }
      }

      if(h1==0&&h2!=0)
      {
        pre->next=h2;
      }

      return res;


    }
};

2.递归实现

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
      if(pHead1==0)return pHead2;
      if(pHead2==0)return pHead1;
      if(pHead1->val>=pHead2->val)
      {
        pHead2->next=Merge(pHead1,pHead2->next);
        return pHead2;
      }
        else
        {
          pHead1->next=Merge(pHead1->next,pHead2);
          return pHead1;
        }

    }
};