链表经典算法OJ题目（2）

1.寻找链表的中间节点

题目链接：876. 链表的中间结点 - 力扣（LeetCode）

53876226b4224dc8b7b7f3db85411bcc.png

我们来直接介绍一个思路：快慢指针

快慢指针是指我们创建创建2个指针，一个为快指针，一个为慢指针，且快指针一次走的步数是慢指针的两倍。两个指针同时往后走，当快指针为空或者快指针->next为空时，此时，慢指针的位置恰好是中间节点。

1.1 节点的个数为奇数

3a5cc9301ab24bb5b11d6912c465d3b4.png

3201bf0d95fc4f0b8d6b69a74321d651.png

79d8f7d76c00485886c142e917e135e0.png

上图为了方便理解，画了两条链表。其实两个指针是在一条链表里面实现的。

节点个数为奇数时，当fast指针走到节点末尾时，slow指针指针的位置恰好是节点的中间位置。

1.2 节点的个数为偶数

6d24a45361c249d4b3e1dc0c51c28588.png

61899d72e76741eb8d9ad6cb52ce5ef1.png

6bf3e8710ddc41f9b05771ba355f4952.png

当节点的个数为偶数时，当fast指针最后为空指针时，slow指针的位置恰好是节点的中间节点。

代码实现

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode*slow=head;
    ListNode*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

注意事项：循环条件不能写成while(fast->next&&fast)，因为当链表的节点个数为偶数个时，fast指针最终会为空指针，则fast->next就会报错，如果按照我上面那样写，当fast为空时，循环条件的表达式就会短路，不会执行后面的fast->next。

2.合并两个有序链表 

做题链接：21. 合并两个有序链表 - 力扣（LeetCode）​​​​​

 

a59ffcbbab6241c3adb0d2f6c6f8c8bd.png

暴力解题思路：直接创建一个新链表，两个链表之间各个节点的数据依次进行比较，数据小的插入新链表。

1df362b82216406295e8f79bc9366acd.png

509f9f4102854ae8963f998e8e2edb94.png

3007576ce04b405e821ac795f4008e0e.png

fa21e0b1155f48ddbcb9e882aa55ed30.png

63c091693dcf4718975e8b0920b8fddf.png

79e06cfc3cd04c2eb89ddfd3a9a99c52.png

b90baaae49fe452d821f86b5a06416cc.png

4ac9d2df60e6405fa53c31c102b4c16d.png

16131afc210c4407a727235a9097bba8.png

6a54d4dbfa174267a73cc31f7d8a2ea2.png

69bb76696e924e1aa926de7ef451aa6f.png

e58547985d474d3d9eb0c797b6b8c83b.png

如上面的过程图所示，数据小对应的节点被拿出来插入新的节点，接着让对应的节点向后走到下一个节点，直到有一条链表走完。

代码实现

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }

    //创建新链表
    ListNode*newhead,*newtail;
    newhead=newtail=NULL;
    //遍历原链表
    ListNode*l1=list1;
    ListNode*l2=list2;
    while(l1&&l2)
    {
        if(l1->val<l2->val)
        {
            if(newhead==NULL)
            {
                newhead=newtail=l1;
            }
            else
            {
                newtail->next=l1;
                newtail=l1;
            }
            l1=l1->next;
        }
        else
        {
            if(newhead==NULL)
            {
                newhead=newtail=l2;
            }
            else
            {
                newtail->next=l2;
                newtail=l2;
            }
            l2=l2->next;
        }
    }
    if(l1)
    {
        newtail->next=l1;
    }
    if(l2)
    {
        newtail->next=l2;
    }
    return newhead;
}

8095d638aa944314954b1b4c876af63e.png

当写完代码我们发现，如上图，有两段一样的代码，这就造成了代码的拥挤，造成有这两段带码的原因：因为新建的头节点和尾节点存在空指针的情况，需要就行判空。

解决方法：建立哨兵位，让哨兵位作为新的头节点，并且哨兵位不存放任何数据。

7d5d152385bf4dc18757f1c230a77f4c.png

优化代码

#include<stdlib.h>
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }
    //建立哨兵位
    ListNode*newhead,*newtail;
    newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
    //遍历原链表
    ListNode*l1=list1;
    ListNode*l2=list2;
    while(l1&&l2)
    {
        if(l1->val<l2->val)
        {
            newtail->next=l1;
            newtail=l1;
            l1=l1->next;
        }
        else
        {
            newtail->next=l2;
            newtail=l2;
            l2=l2->next;
        }
    }
    if(l1)
    {
        newtail->next=l1;
    }
    if(l2)
    {
        newtail->next=l2;
    }
    ListNode*next=newhead->next;
    free(newhead);
    newhead=NULL;
    return next;
}

注意事项：使用malloc函数，最后要记得销毁掉，不然可能会造成内存溢出。

我们要返回的节点是哨兵位的下一个节点，因为返回前要将哨兵位销毁掉，所以我们要提前将哨兵位的下一个节点存储起来。