LinCode 165.合并两个排序链表

思路
两个指针，分别指向两个链表，从头开始遍历
另一个指针指向新创建的节点，将排序好的节点串联起来
注意此题是允许重复元素的

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param l1: ListNode l1 is the head of the linked list
     * @param l2: ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode * mergeTwoLists(ListNode * l1, ListNode * l2) {
        // write your code here
        
        ListNode *pl1 = l1;
        ListNode *pl2 = l2;
        ListNode *phead = new ListNode(0);    //新链表的头结点
        ListNode *p = phead;
        
        while (pl1!=NULL && pl2!=NULL)
        {
            if(pl1->val < pl2->val)
            {
                p->next = pl1;
                pl1 = pl1->next;
            }
            else
            {
                p->next = pl2;
                pl2 = pl2->next;
            }
            p = p->next;
        }
        
        while(pl1 != NULL)
        {
            p->next = pl1;
            pl1 = pl1->next;
            p = p->next;
        }
         while(pl2 != NULL)
        {
            p->next = pl2;
            pl2 = pl2->next;
            p = p->next;
        }
        
        return phead->next;
    }
};

标准答案

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

class Solution {
public:
    /*
    题意：合并两个有序链表
    模拟一轮归并排序
    */
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *tmp = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                tmp->next = l1;
                l1 = l1->next;
            } else {
                tmp->next = l2;
                l2 = l2->next;
            }
            tmp = tmp->next;
        }
        if (l1 != NULL) tmp->next = l1;
        else tmp->next = l2;
        return dummy->next;
    }
};

看完标答之后真的感觉自己多此一举了，最后的循环赋值没有意义，直接串联接上就好了。
但是答案中直接改变了两个链表的首地址真的好吗？这两个链表没用了？

LinCode 165.合并两个排序链表

相关推荐