165 合并两个排序数组

原题网址：https://www.lintcode.com/problem/merge-two-sorted-lists/description

描述

将两个排序链表合并为一个新的排序链表

您在真实的面试中是否遇到过这个题？  是

样例

给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。

标签

链表

 

思路：逐个比较l1与l2的结点，将较小的挂载在结果链表上。

小技巧：可以创建一个数据无效的结点作为标志头节点，返回其next。

 

AC代码：

/**
 * 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
    if (l1==NULL)
    {
        return l2;
    }
    if (l2==NULL)
    {
        return l1;
    }
    ListNode n(0);//标志头结点，返回其下一个节点;
    ListNode *p=&n;
    ListNode * cur1=l1;
    ListNode * cur2=l2;
    while(cur1!=NULL&&cur2!=NULL)
    {
        if (cur1->val<=cur2->val)
        {
            p->next=cur1;
            cur1=cur1->next;
            p=p->next;
        }
        else
        {
            p->next=cur2;
            cur2=cur2->next;
            p=p->next;
        }
    }
    if (cur1!=NULL)
    {
        p->next=cur1;
    }
    if (cur2!=NULL)
    {
        p->next=cur2;
    }
    return n.next;
    }
};