《链表面试基础看点：这里不止“快慢指针”的完美实现，更懂“哨兵节点”的巧妙运用》

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) 
{
    //创建快慢指针
    ListNode* fast, *slow;

    //首先都指向头节点
    fast = head;
    slow = head;

    //循环条件将两种情况都包含
    while(fast != NULL && fast->next != NULL)//条件换顺序？
    {
        //慢指针移动一节点
        slow = slow->next;
        //快指针移动两个节点
        fast = fast->next->next;
    }

    //返回slow
    return slow;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{

    //判断两个链表是否是空链表
    if(list1 == NULL)
    {
        return list2;//直接返回list2
    }
    if(list2 ==NULL)
    {
        return list1;//直接返回list1
    }

    //创建空链表：空的首节点
    ListNode* newhead, *newtail;
    newhead = newtail = NULL;

    //两个指向指针
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    //遍历原链表
        //先将相同长度内的节点进行比较
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->val < l2->val)
        {
            //l1尾插
            //第一回尾插，链表为空
            if(newhead == NULL)
            {
                newhead = newtail = l1;//为头、为尾
            }
            //后续尾插
            else
            {
                newtail->next = l1;
                newtail = newtail->next; //尾后移
            }
            l1 = l1->next;//链表1后移
        }
        else
        {
            //l2尾插
            //第一回尾插，链表为空
            if(newhead == NULL)
            {
                newhead = newtail = l2;//为头、为尾
            }
            //后续尾插
            else
            {
                newtail->next = l2;
                newtail = newtail->next; //尾后移
            }
            l2 = l2->next;
        }     

        //跳出循环，代表有链表走到了空
        if(l1)
        {
            newtail->next = l1;
        }

        if(l2)
        {
            newtail->next = l2;
        }
    }
    return newhead;
}

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{

    //判断两个链表是否是空链表
    if(list1 == NULL)
    {
        return list2;//直接返回list2
    }
    if(list2 ==NULL)
    {
        return list1;//直接返回list1
    }

    //创建非空链表：申请一份节点的空间
    ListNode* newhead, *newtail;
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));

    //两个指向指针
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    //遍历原链表
        //先将相同长度内的节点进行比较
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->val < l2->val)
        {
            //l1尾插
            newtail->next = l1;
            newtail = newtail->next; //尾后移
            l1 = l1->next;//链表1后移
        }
        else
        {
            //l2尾插
            newtail->next = l2;
            newtail = newtail->next; //尾后移
            l2 = l2->next;
        }     
        //跳出循环，代表有链表走到了空
        if(l1)
        {
            newtail->next = l1;
        }

        if(l2)
        {
            newtail->next = l2;
        }
    }
    //手动申请的空间自己要释放
    //释放前，保存节点
    ListNode* retnewhead = newhead->next;
    free(newhead);
    newhead = NULL;
    return retnewhead;
}