剑指offer-合并两个排序的链表

本文为剑指 offer 系列第十八篇。
主要知识点是链表，仍然是在遍历链表的基础上进行相关操作，非常经典。

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路

找两个指针分别指向两个有序链表的头结点，然后依次找最小值放到存放结果的链表之中即可。
要记得考虑一个链表遍历完而另一个链表没有遍历完的情况。

解题代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* phead1, ListNode* phead2)
    {
         if(!phead1 && !phead2) return NULL;
        if(!phead1) return phead2;
        if(!phead2) return phead1;
        ListNode *head = NULL, *tail = NULL;
        ListNode *p1= phead1,*p2 = phead2;
        while(p1 && p2){
            if(p1->val <= p2->val){
                ListNode* temp = new ListNode(p1->val);
                if(!head){
                    head = temp;
                    tail = temp; 
                }
                tail->next = temp;
                tail = tail->next;
                p1= p1->next;
            }else{
                ListNode* temp = new ListNode(p2->val);
                  if(!head){
                    head = temp;
                    tail = temp; 
                }
                tail->next = temp;
                tail = tail->next;
                p2= p2->next;
            }
        }
        if(!p1 && !p2) return head;
        while(p1){
            ListNode* temp = new ListNode(p1->val);
                if(!head){
                    head = temp;
                    tail = temp; 
                }
                tail->next = temp;
                tail = tail->next;
                p1= p1->next;
        }
        while(p2){
            ListNode* temp = new ListNode(p2->val);
                  if(!head){
                    head = temp;
                    tail = temp; 
                }
                tail->next = temp;
                tail = tail->next;
                p2= p2->next;
        }
        return head;
    }
};

时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！