9.15 链表问题（续）

两个排序链表合并

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

有两种解法：
1、迭代
2、递归
需要注意的是，迭代是next赋值（a->next = l1），所以返回值也要next，
而递归是直接赋值（pNewHead = pHead1），所以返回头节点就可以了。

迭代方法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head =  new ListNode(0);
   //ListNodelist=newListNode(0) 初始化一个节点值为0的空节点，最常用最正规写法；
        ListNode* a=head;
        while(l1 != nullptr && l2!=nullptr)
        {
            if(l1->val < l2->val){
                a->next = l1;
                l1 = l1->next;
            }else{
                a->next = l2;
                l2 = l2->next;
            }
            a = a->next;
        }
        if(l1==nullptr){
            a->next = l2;
        }else{
            a->next = l1;
        }
        return head->next;
    }
};

递归方法

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

删除排序链表中的重复元素

单指针

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head||!head->next)
            return head;
        ListNode* p=head;
        while(p->next!=NULL&&p!=NULL)
        {
            if(p->val == p->next->val)
            {
                p->next=p->next->next;
            }
            else 
                p=p->next;
        }
        return head;
    }
};

双指针

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return head;
        ListNode* p=head;//慢指针
        ListNode* q=head->next;//快指针
        while(p->next!=NULL)
        {
            if(p->val==q->val)//找到重复元素
            {
                if(q->next==NULL)//快指针后面若没有元素直接剔除
                    p->next=NULL;
                else//快指针后有元素
                {
                    p->next=q->next;
                    q=q->next;
                }
            }
            else //元素不相等
            {
                p=p->next;
                q=q->next;
            }
        }
        return head;
    }
};