两个排序链表合并

LeetCode 21. Merge Two Sorted Lists
已知两个已排序链表头节点指针L1，L2，将这两个链表合并，合并后仍为有序的，返回合并后的头节点。

数据结构

struct ListNode{
    int val;
    ListNode * next;
    ListNode(int x): val(x),next(NULL){}
};

class Solution{
public:
    ListNode* mergeTwoLists(ListNode *L1,ListNode *L2){}
}

算法设计

比较l1和l2指向的节点，将较小的节点插入到pre指针后，并向前移动较小节 点对应的指针与pre指针，直到l1与l2指针有一个为空指针。最后再连接不为空的那段链表(l1或l2)。

class Solution{
public:
    ListNode * mergeTwoLists(ListNode *L1,ListNode *L2){
    ListNode temp_head(0);//设置临时头节点temp_head
    ListNode *pre = &temp_head;
while(L1 && L2){
    if(L1->val < L2->val){
        pre->next = L1;
        L1 = L1->next;
    else{
        pre->next = L2;
        L2 = L2->next;    
    }
    pre = pre->next
           
}
if(L1){//如果L1有剩余
pre->next =L1;
}
if(L2){
pre->next = L2;
}
return temp_head.next  
}

}
}