反转链表、链表的中间结点、合并两个有序链表【LeetCode刷题日志】

一、反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：翻转单链表指针方向

这里解释一下三个指针的作用：

n1：记录上一个节点，如果是第一个就指向空

n2：记录此节点的位置

n3：记录下一个节点的位置，让翻转后能找到下一个节点，防止丢失指针的地址

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
    {
        return NULL;
    }
    //初始条件
    struct ListNode* n1 = NULL,*n2 = head,*n3 = n2->next;
    //结束条件
    while(n2)
    {
        //迭代过程
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
        
    }
    return n1;
}

思路二:头插法

取原链表节点头插到新链表

/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;

        //头插
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}

二、链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一：单指针法

时间复杂度：O(N*1.5)，其中 N 是给定链表的结点数目。
空间复杂度：O(1)，只需要常数空间存放变量和指针。

我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    int n = 0;
    struct ListNode*cur = head;
    while(cur != NULL)
    {
        ++n;
        cur = cur->next;
    }
    int k = 0;
    cur = head;
    while(k < n/2)
    {
        ++k;
        cur = cur->next;
    }
    return cur;
}

思路二：快慢指针法

时间复杂度：O(N)，其中 N 是给定链表的结点数目。
空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。

我们可以优化思路一，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

三、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路一（迭代法）:

定义一个头指针和一个尾指针，从小到大依次尾插，直到一个链表为空时结束

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL)    
    return l2;
    if(l2 == NULL)
    return l1;
    struct ListNode* head = NULL, *tail = NULL;
    while(l1 != NULL && l2 != NULL)
    {
        if(l1->val < l2->val)
        {
            //尾插
            if(tail == NULL)
            {
                head = tail = l1;
            }
            else{
                tail->next = l1;
                tail = tail->next;
            }
            l1 = l1->next;
        }
        else{
            if(tail == NULL)
            {
                head = tail = l2;
            }
            else{
                tail->next = l2;
                tail = tail->next;
            }
            l2 = l2->next;
        }
    }
    if(l1)
        tail->next= l1;
    if(l2)
        tail->next= l2;
    return head;
}

优化一:

先确定头结点，然后再循环判断val大小，尾插

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL)    
    return l2;
    if(l2 == NULL)
    return l1;
    struct ListNode* head = NULL, *tail = NULL;
    //先确定头节点
    if(l1->val < l2->val)
    {
        head = tail =l1;
        l1 = l1->next;
    }else{
        head = tail =l2;
        l2 = l2->next;
    }

    while(l1 && l2)
    {
            //尾插
        if(l1->val < l2->val)
        {   
            tail->next = l1;
            l1 = l1->next;
        }
        else{
            tail->next = l2;
            l2 = l2->next;
            }
    tail = tail->next;
    }
    if(l1)
        tail->next= l1;
    if(l2)
        tail->next= l2;
    return head;
}

优化二:

设置一个哨兵位的头节点，然后再去尾插。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL)    
    return l2;
    if(l2 == NULL)
    return l1;
    struct ListNode* head = NULL, *tail = NULL;
    //哨兵位的头节点
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while(l1 && l2)
    {
            //尾插
        if(l1->val < l2->val)
        {   
            tail->next = l1;
            l1 = l1->next;
        }
        else{
            tail->next = l2;
            l2 = l2->next;
            }
    tail = tail->next;
    }
    if(l1)
        tail->next= l1;
    if(l2)
        tail->next= l2;
    struct ListNode* first = head->next;
    free(head);
    return first;
}

思路二（递归法）：

（这是题解中大佬的一个解法）以迭代的思路写递归，尤为惊人！！！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    /*if判断：
    1.如果l1为空，返回l2
    2.如果l2为空，返回l1
    3.如果l1的值小于l2，比较l1的next值和l2，并把值赋给l1的下一个；返回l1
    4.反之，比较l1和l2的next值，并把值赋给l2的下一个；返回l2
    */
    if (l1 == NULL) {
            return l2;
        } else if (l2 == NULL) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
}