链表OJ（上）

前言：欢迎来到链表OJ海洋，你准备好游泳圈了吗？上次学习了单链表的增删查改，这次我们就先拿几道OJ题来试试手。

1、移除链表元素

链接：

https://leetcode-cn.com/problems/remove-linked-list-elements/description/

题目：

题解：

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


struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        if(cur->val!=val)
        {
            prev=cur;
            cur=cur->next;
        }
        else
        {
            struct ListNode* next=cur->next;
            //这里是防止头就是要除去的数，导致头被free掉以后返回NULL
            if(prev==NULL)
            {
                head=next;
                free(cur);
                cur=next;
            }
            else
            {
                prev->next=next;
                free(cur);
                cur=next;
            }
        }
    }
    return head;
}

讲解：

三个指针，cur=head，判断cur->val与要删除的值是否相等，如果不相等就继续往前走，如果相等，就将prev->next指向next，然后free掉这个要除去的数。这是常规情况下，但我们做题，就是要考虑所有的可能，那么还会出现哪些情况呢？如果有连续要去除的数呢，如果head就是要除去的数呢？接下来我们看看上面那种情况是不是也适合这两种情况。

我们发现这种连续的也是适用的。

但是这种头就是要除去的数，就存在着一定的问题，当cur和next继续往前走，走到4，直到尾，头已经被free掉了，但是我们要返回的是头，所以等(cur->val==val)&&(prev==NULL)的时候， 头也要跟着走，也就是head跟着next走（因为cur->val==val，是要除去的数，所以直接跳过）。

2、反转一个单链表

链接：

https://leetcode-cn.com/problems/reverse-linked-list/description/

题目：

我们可以直接将每个元素指向它的前一个，即如图：

题解：

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


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        //如果给的空链表，那就要返回空链表
        if(head==NULL)
        {
            return NULL;
        }
        struct ListNode* next=cur->next;
        cur->next=prev;
        prev=cur;
        head=cur;
        cur=next;
        //防止最后next走到NULL以后还往后走
        if(next)
        {
            next=next->next;
        }
    }
    return head;
}

讲解：

head跟着cur走，，cur跟着next走，走到尾，head成为新的头。

这里还有一种方法，根据我们单链表学的增删查改，我们可以对该链表进行头插（但其实和上一种方法思想是一致的）：

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


struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newhead=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;
}

3、求链表的中间结点

链接：

求链表的中间结点

题目:

按照我们通常的做法，像我们求数组的中间数时，会选择把数组全部遍历一遍，那么在链表这里也一样，我们可以选择把链表全部遍历一遍，求出链表的长度，然后找中间结点，但这样时间复杂度大大增加，所以，我们有一种更简便的方法，采用快慢指针！

题解：

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


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

讲解：

所谓快慢指针就是一个走快点，一个走慢点，这里我们定义了快指针fast和慢指针slow，slow每走一步，fast走两步，那么当链表元素个数为奇数且最后当fast->next指向空的时候，slow指向的一定是链表的中间结点，而题目中示例2也说明，当链表元素个数为偶数时，这时会有两个中间结点，那我们取的是后面一个，所以，当元素个数为偶数且最后fast指向空的时候，slow指向的也一定是中间结点。

4、求链表中倒数第K个结点

链接：

牛客：求链表倒数第K个结点

题目：

通过上个题目以后，这道题是不是就感觉简单很多了呢？没错，这道题和上一道如出一辙。

题解：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* fast=pListHead;
    struct ListNode* slow=pListHead;
    while(k--)
    {
        if(fast==NULL)
            return NULL;
        fast=fast->next;
    }
    
    while(fast)
    {
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

讲解：

这里和上一道题一样，也采用快慢指针的方法，只不过，这一次的快指针是先走K步，然后慢指针和快指针一起走，当最后快指针走到尾的时候，慢指针指向的就是倒数第K个结点了。

以防万一，我们再试一个，假如是找倒数第三个呢？

我们发现也是没问题的，这样时间复杂度就大大减少了。

5、合并两个有序链表

链接：

合并两个有序链表

题目：

题解：

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


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* tail=NULL;
    struct ListNode* head=NULL;

    if(list1==NULL)
    {
        return list2;
    }

    if(list2==NULL)
    {
        return list1;
    }
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            if(head==NULL)
            {
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=list1;
            }
            list1=list1->next;
        }
        else
        {
            if(head==NULL)
            {
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }
    }

    //当其中有个链表已经走完，另一个链表还剩下的时候，就把剩下的全部接上去
    if(list1)
    {
        tail->next=list1;
    }
    if(list2)
    {
        tail->next=list2;
    }
    return head;
}

讲解：

首先判断第一个，如果head==NULL，那么就把小的那个给head，tail跟着小的走，然后两个链表也依次走，哪边的值小，就哪个走，最后到有一个链表已经空，就结束循环，如果另一个链表还有剩余，由于两个链表都是有序的，所以直接把剩余的那个链表接在尾部。

今天的OJ到此结束，你是否有感觉收获呢！