Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

题目意思为合并两个链表，不能用额外的空间（新链由两个链拼接而成）

思路：

比较简单，直接定义两个指针，分别指向两条链，比较所指向节点的大小 如果指针指向的值为小的，那么就让新链指向小的，同时该指针往后移动

，新链的当前指针也往后移动。直到两条链中有一条遍历到了结尾，然后将剩余的链拼接到新链

代码如下：

<span style="font-size:18px;">/**
 * 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) {
        
    if(l1==NULL)
        return l2;
    if(l2==NULL)
        return l1;
    
    ListNode *p,*q;
    p=l1;
    q=l2;
    
    ListNode *result=new ListNode(0);
    ListNode *temp =result;
    while(p&&q)
    {
        if(p->val<q->val)
        {
            temp->next=p;
            temp=p;
            p=p->next;
            
        }
        else
        {
            temp->next=q;
            temp=q;
            q=q->next;
        }
    }
    
    if(p)
    {
        temp->next=p;
    }
    if(q)
    {
        temp->next=q;
    }
        return result->next;
    }
};</span>

Merge Two Sorted Lists leetcode