21. Merge Two Sorted Lists

• 出错误的解法一

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   */
  class Solution
  {
  public:
      ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
          ListNode* newnode = new ListNode(0);
        newnode->next = NULL;
        ListNode* pre = newnode;
        
        if(l1 == NULL && l2 == NULL)
        {
            return NULL;
        }
        
        if(l1 == NULL && l2 != NULL)
        {
            return l2;
        }
        
        if(l2 == NULL && l1 != NULL)
        {
            return l1;
        }
        
        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val == l2->val)
            {
                //l1再前 l2再后 l1 l2均插入新队列
                pre->val = l1->val;
                pre->next = new ListNode(0);
                pre->val = l2->val;
                pre->next = NULL;
                l1 = l1->next;
                l2 = l2->next;
            }
            else if(l1->val > l2->val)
            {
                //l2插入新队列
                pre->val = l2->val;
                pre->next = new ListNode(0);
                l2 = l2->next;
            }
            else
            {
                //l1插入新队列
                pre->val = l1->val;
                pre->next = new ListNode(0);
                l1 = l1->next;
            }
            
            
        }
        
        while(l1 != NULL)
        {
            pre->next = new ListNode(0);
            pre->val = l1->val;
            l1 = l1->next;
        }
        
        while(l2 != NULL)
        {
            pre->next = new ListNode(0);
            pre->val = l2->val;         
            l2 = l2->next;
        }
        
        return newnode;
      } 
  };

• 出错误的解法二

  class Solution
  {
  public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode* pre = NULL;
        ListNode* newnode = pre;  //尾指针初始状态下指向头节点
  
        if (l1 == NULL && l2 == NULL)
        {
            return NULL;
        }
  
        if (l1 == NULL && l2 != NULL)
        {
            return l2;
        }
  
        if (l2 == NULL && l1 != NULL)
        {
            return l1;
        }
  
        while (l1 != NULL && l2 != NULL)
        {
            if (l1->val == l2->val)
            {
                pre = new ListNode(0);
                pre->next = NULL;
                pre->val = l1->val;
                pre = pre->next;
                l1 = l1->next;
            }
            else if (l1->val > l2->val)
            {
                //l2插入新队列
                pre = new ListNode(0);
                pre->next = NULL;
                pre->val = l2->val;
                pre = pre->next;
                l2 = l2->next;
            }
            else
            {
                //l1插入新队列
                pre = new ListNode(0);
                pre->next = NULL;
                pre->val = l1->val;
                pre = pre->next;
                l1 = l1->next;
            }
  
  
        }
  
        while (l1 != NULL)
        {
            pre = new ListNode(0);
            pre->next = NULL;
            pre->val = l1->val;
            pre = pre->next;
            l1 = l1->next;
        }
  
        while (l2 != NULL)
        {
            pre = new ListNode(0);
            pre->next = NULL;
            pre->val = l2->val;
            pre = pre->next;
            l2 = l2->next;
        }
  
        return newnode;
    }
  };

• AC版代码1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
  {
      ListNode* newnode = new ListNode(0);  //头节点
      ListNode* pre = newnode; //尾指针初始状态下指向头节点

      if (l1 == NULL && l2 == NULL)
      {
          return NULL;
      }

      if (l1 == NULL && l2 != NULL)
      {
          return l2;
      }

      if (l2 == NULL && l1 != NULL)
      {
          return l1;
      }

      while (l1 != NULL && l2 != NULL)
      {
          if (l1->val == l2->val)
          {
              pre->next = new ListNode(0);
              pre = pre->next;
              pre->val = l1->val;
              l1 = l1->next;
          }
          else if (l1->val > l2->val)
          {
              //l2插入新队列
              pre->next = new ListNode(0);
              pre = pre->next;
              pre->val = l2->val;
              l2 = l2->next;
          }
          else
          {
              //l1插入新队列
              pre->next = new ListNode(0);
              pre = pre->next;
              pre->val = l1->val;
              l1 = l1->next;
          }


      }

      while (l1 != NULL)
      {
          pre->next = new ListNode(0);
          pre = pre->next;
          pre->val = l1->val;
          l1 = l1->next;
      }

      while (l2 != NULL)
      {
          pre->next = new ListNode(0);
          pre = pre->next;
          pre->val = l2->val;
          l2 = l2->next;
      }
      pre->next = NULL;
      return newnode->next;
  }
};

这一版代码其实有很大的优化空间，首先不需要一开始对 l1 和 l2 的判空，因为在while循环中已经处理过这个问题。经过优化后的代码如下:

• AC版代码2

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution
    {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
        {
            ListNode* newnode = new ListNode(0);  //头节点
            newnode->next = NULL;
            ListNode* pre = newnode; //尾指针初始状态下指向头节点
    
            while (l1 != NULL && l2 != NULL)
            {
                if (l1->val == l2->val)
                {
                    pre->next = new ListNode(0);
                    pre = pre->next;
                    pre->val = l1->val;
                    l1 = l1->next;
                }
                else if (l1->val > l2->val)
                {
                    //l2插入新队列
                    pre->next = new ListNode(0);
                    pre = pre->next;
                    pre->val = l2->val;
                    l2 = l2->next;
                }
                else
                {
                    //l1插入新队列
                    pre->next = new ListNode(0);
                    pre = pre->next;
                    pre->val = l1->val;
                    l1 = l1->next;
                }
    
    
            }
    
            while (l1 != NULL)
            {
                pre->next = new ListNode(0);
                pre = pre->next;
                pre->val = l1->val;
                l1 = l1->next;
            }
    
            while (l2 != NULL)
            {
                pre->next = new ListNode(0);
                pre = pre->next;
                pre->val = l2->val;
                l2 = l2->next;
            }
            pre->next = NULL;
            return newnode->next;
        }
    };

• 另一种思路

这道题目并没有说不可以更改l1和l2，因此又有如下代码：

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution
     {
     public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
        {
            ListNode* headnode = new ListNode(0);
            headnode->next = NULL;
            ListNode* pre = headnode;  //尾指针初始状态下指向头节点
            
            //注意题目中l1和l2都没有头节点
            while(l1 != NULL && l2 != NULL)
            {
                if(l1->val > l2->val)
                {
                    pre->next = l2;
                    pre = pre->next;
                    l2 = l2->next;
                }
                else
                {
                    //相等 或 l1 比 l2小 都应该执行这里
                    pre->next = l1;
                    pre = pre->next;
                    l1 = l1->next;
                }
                
            }
            
            if(l1)
            {
                pre->next = l1;
                l1 = NULL;
            }
            
            if(l2)
            {
                pre->next = l2;
                l2= NULL;
            }
            
            return headnode->next;
        }
     };

这次代码的思路是直接把l1或者 l2 的节点摘除贴在pre后面。

21. Merge Two Sorted Lists

原文：https://www.cnblogs.com/Manual-Linux/p/12113240.html