[数据结构与算法]【leetcode】剑指 Offer 25. 合并两个排序的链表（简单）

【leetcode】剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

解题思路：

初始化一个指针res指向头节点，遍历两个链表l1，l2，如果当前节点的值l1 -> val > l2 -> val，则res指向l2，l2指针后移一位；如果当前节点的值l1 -> val <= l2 -> val，则res指向l1，l1指针后移一位；最后其中一个链表遍历结束，退出循环，假设l1遍历结束，l2还有未遍历结束，那么res指向l2，否则指向l1。最后返回head.next。

代码：

C：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* p1 = l1;
    struct ListNode* p2 = l2;
    struct ListNode head;   //定义一个节点；struct ListNode *head只是一个指针。
    struct ListNode* res = &head;
    while (p1 && p2) //链表l1和链表l2都没有遍历结束
    {
        if (p1 -> val > p2 -> val)
        {
            res -> next = p2;
            p2 = p2 -> next;      
        }
        else
        {
            res -> next = p1;
            p1 = p1 -> next;
        }
        res = res -> next;
    }
    res -> next = p1 ? p1 : p2;  //链表l1或l2未遍历完的部分直接拼接到res后面
    return head.next;
}

备注：

1、return head.next; 没有搞明白为什么要返回head.next，返回head为什么不行？
head只是一个节点（结构体），程序过程中只对head.next赋值过。所以需要返回head.next。
struct ListNode head;
struct ListNode* res = &head;
res -> next = p2;

2、struct ListNode head; 定义 struct ListNode *head;为什么会有问题
struct ListNode *head会给指针head分配四个字节空间大小（32位系统），给head->next赋值会因空间大小不够而出错。