连线法合并两个有序链表

1.设置表头节点dummy的作用：统一循环内的操作；如果仅仅使用头指针head，则无法做到统一，必须单独写一个if判断。

2.使用已知的两个链表头指针l1、l2作为双指针

3.从dummy节点出发，每次比较l1->val和l2->val的大小，小的被链接到rear上

4.这种方法并没有破坏原有的两个链表，而是直接把他们拼接成了一个，既不用新开辟储存空间，也不用释放原来的空间。

LinkCode题165：“合并两个排序链表”：

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

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 q=ListNode(0);
        ListNode* dummy=&q;/*由于要求返回头指针，故将表头节点dummy创建在栈上避免内存泄漏*/
        ListNode* rear=dummy;
        while(l1!=nullptr&&l2!=nullptr){
            if(l1->val<l2->val){
                rear->next=l1;
                l1=l1->next;
            }else{
                rear->next=l2;
                l2=l2->next;
            }
            rear=rear->next;
        }
        rear->next=l1==nullptr?l2:l1;
        return dummy->next;
    }
};