21. 合并两个有序链表

文|Seraph

01 | 问题

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

02 |解题

初解：

使用三个指针，两个指针分别轮训两个链表，还有一个指针用来改动指针指向来重新排序链表。
但有些临界情况没想好怎么整到一个循环里，导致代码量过多。

/**
 * 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 *p1=l1;
        ListNode *p2=l2;
        ListNode *p3=nullptr;
        ListNode *result = nullptr;
        if(l1==nullptr)
            return l2;
        if(l2==nullptr)
            return l1;
         if(l1->val<=l2->val)
         {
             result = l1;
             p3=p1;
             p1=p1->next;
         }
        else
        {
            result = l2;
            p3=p2;
            p2=p2->next;
        }
        while(p1!=nullptr&&p2!=nullptr)
        {
            if(p1->val<=p2->val)
            {
                p3->next=p1;
                p1=p1->next;
                p3=p3->next;
            }
            else
            {
                p3->next=p2;
                p2=p2->next;
                p3=p3->next;
            }
            
        }
        if(p1!=nullptr)
        {
            p3->next=p1;
        }
        if(p2!=nullptr)
        {
            p3->next=p2;
        }
        
       return result;
    }
};

终解：

如下新增一个头节点，能有效省去专门对第一个节点的处理。

• 迭代方法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)   
        {
            if(l1 == NULL) return l2;
            if(l2 == NULL) return l1;
            ListNode* l3 = new ListNode(-1);//新建一个头结点
            ListNode* p = l1;
            ListNode* q = l2;
            while(p != NULL&&q != NULL)
            {
                if(p->val <= q->val) 
                {
                    l3->next = p;              
                    p = p->next;
               }   
                else
                {
                    l3->next = q;               
                    q = q->next;
                }
                l3 = l3->next;              
            }
            if(p == NULL) l3->next = q;
            if(q == NULL) l3->next = p;
           return l1->val<=l2->val?l1:l2;  //通过条目判断语句返回链表的首地址
        }
};

由于这个排序问题可以拆分成一个个比较的小问题，所以可以考虑使用递归的方式处理，这样思路会很清晰。迈入下

• 递归方法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        if(l1->val<l2->val)
        {
            l1->next=mergeTwoLists(l1->next,l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        }
        
    }
};

03 | 积累知识点

1. 链表处理时，假设一个占位的头结点的存在，很使代码减少专门对头结点处理的情况。从而使代码更加清晰。
2. 代码不仅仅要追求效率，还需要书写得让读代码者一目了然，逻辑清晰。
3. 尽量较少特殊情况的处理。能归为一类处理，就尽量归为一类处理，减少代码量的同时，也减少对代码的理解时间。