链表OJ经典题浅刷＜ 1 ＞（看完不再害怕链表题）

🎈：经典之所以被称为经典，是因为在大部分的题目中都能够找到它们的影子，经典题的解题思路已潜移默化的渗透到每道题中，只有我们掌握好经典题的解题思路，我想我们解题能力也定会更上一层楼。

🎈：这篇博客主要是对一些经典的单链表题进行讲解，让你对单链表OJ题不再恐惧！！👨🏻‍💻

正文开始

一移除链表元素

原题链接：

移除链表元素 - 力扣（LeetCode） (leetcode-cn.com)

** 思路：**

我们可以创建一个指针变量cur来遍历链表，当cur->val==val时，我们就需要删除此结点，但链表是连续的，free结点的同时还需要保留上一个结点的地址，所以我们用指针变量prev来保存上一个结点的地址，同时我们做这道题也要考虑到特殊情况，比如头结点就是所要删除的结点，以及链表中间有好几个结点都是需要删除的结点。

错误代码：
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(cur);
            prev->next = next;
            cur = next;
        }
    }
    return head;
}
⚠此种代码并未考虑首结点即为所要删除结点的情况即为情况三，当首结点为所要删除结点，那么prev就是空指针，此时prev->next=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;
            if (prev == NULL)
            {
                free(cur);
                head = next;
                cur = next;
            }
            else
            {
                free(cur);
                prev->next = next;
                cur = next;
            }
        }
    }
    return head;
}

二反转链表

原题链接：

反转链表 - 力扣（LeetCode） (leetcode-cn.com)

** 法一：三指针逆转**

我们要做的是把链表逆置，我们可以想到只要把上图中的箭头反转就可以实现链表的逆置

** **思路：

我们可以初始化指针n1为空指针，然后将头结点的地址放入n2中，反转后原来的头结点的next指向空指针，此时我们需要再创建一个指针变量n3来存放n2的下一个结点的地址，因为原本的存放n3地址的n2->next已经被赋值为n1的地址了。当n2指向最后一个结点时反转完成，但此时n3为空指针，n3=n3->next会导致程序报错，所以我们加上一个判断条件，如果n3为空指针时，不执行n3=n3->next.
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
        return NULL;
    struct ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;//当n2为空指针时，这里就会报错

    while (n2)
    {
        n2->next = n1;

        n1 = n2;
        n2 = n3;

        if (n3)
            n3 = n3->next;
    }
    return n1;
}
法二：头插法

思路：

我们可以定义一个新的指针变量cur遍历链表，然后创建一个新的链表，头结点newHead初始化为空指针。然后cur取原链表结点，头插到newHead所在的链表。然后更新newHead，需要注意的是当我们将原链表的结点拿下来后我们还要创建一个新的指针变量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;
}

三链表的中间结点

原题链接：

链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)

** 法一：暴力遍历**

思路：

直接遍历链表求出结点个数，然后结点个数除以2，得到的就是链表的中间结点位置，此种方法遍历链表两遍，

** 法二：快慢指针**

思路：

创建两个指针变量slow和fast，刚开始都指向链表的头结点，然后slow向前移一步的同时，fast向前移动两步，如果链表的结点为奇数个，当fast指向最后一个结点时，slow指向的就是中间结点，如果为偶数个，则当fast为空指针，slow指向的就是中间结点。
struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}
**⚠:**需要注意的是fast&&fast->next必须是fast在前，fast->next在后。因为条件先判断的是&&左边的，如果链表为偶数个，那么当fast为空时才停止。此时fast->next会报错。

四链表中倒数第k个结点

原题链接：

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

法一：逆向思维

思路：

我们可以先遍历链表求出链表的长度，设所求链表的总长度为N，要求链表的倒数第K个结点就是求链表的正数第N-K+1个结点。此种方法仍是遍历链表两遍。

法二：快慢指针

思路：

我们创建两个指针变量slow和fast，刚开始都指向链表的头结点，然后fast先走K步，fast走完后，slow和fast同步走，当fast指向空指针时，slow所指向的结点就是倒数第K个结点。

**⚠:**这里容易忽视当K大于链表长度这种情况，当K大于链表长度，我们返回空指针。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    struct ListNode* slow, * fast;
    slow = fast = pListHead;
    // fast 先走K步
    while (k--)
    {
        //K大于链表长度
        if (fast == NULL)
            return NULL;

        fast = fast->next;
    }

    while (fast)
    {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}
    

五合并两个有序链表

原题链接：

合并两个有序链表 - 力扣（LeetCode） (leetcode-cn.com)

思路：

这道题的思路和我们以前用的归并思想一样，我们创建指针变量list1和list2来遍历链表，同时创建指针变量head，初始化为空指针，然后创建指针变量tail用来保存新链表的尾端，因为当链表结点插入到新的链表的尾端，尾端地址会发生改变。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //如果两个合并的链表中有个空链表，则直接返回另外一个链表
    if (list1 == NULL)
        return list2;

    if (list2 == NULL)
        return list1;

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

            list1 = list->next;
        }
        else
        {
            if (tail == NULL)
            {
                head = tail = list2;
            }
            else
            {
                tail->next = list2;
                tail = list2;
            }

            list2= list2->next;
        }
    }
    //如果list1先遍历完则新链表的最后一个结点指向的下一个结点为list2，反之亦然。
    if (list1)
    {
        tail->next = list1;
    }

    if (list2)
    {
        tail->next = list2;
    }

    return head;
}

上面的方法用的是无头单链表，我们这一次用带头结点的单链表。

用带哨兵的单链表后就不用考虑list1和list2是不是空指针。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
        
        struct ListNode* head = NULL, * tail = NULL;
        //带哨兵位的
        head = tail =(struct ListNode*)malloc(sizeof(struct ListNode));
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                
                    tail->next = list1;
                    tail = list1;
                    list1 = list1->next;
            }
            else
            {
                    tail->next = list2;
                    tail = list2;
                    list2= list2->next;
            }
        }
        //如果list1先遍历完则新链表的最后一个结点指向的下一个结点为list2，反之亦然。
        if (list1)
        {
            tail->next = list1;
        }
    
        if (list2)
        {
            tail->next = list2;
        }
    
        struct ListNode* list = head->next;
        free(head);
        head=NULL;
        return list;
    }

下面这道题将是本篇博客的压轴题，是蘑菇街2019年的校招笔试题，勇者不惧，题来！！！👨🏻‍💻

六链表分割

原题链接：

链表分割_牛客题霸_牛客网 (nowcoder.com)

**这道题题目描述真是的写的言简意骇，出题人甚至都懒得给你测试样例，着实让人摸不着头脑，下面我们来分析一下它的大致意思。 **

思路：

遍历原链表，同时创建两个新的链表，把<x的插入链表1，把>=x的插入到链表2，然后再把链表1和链表2链接起来。

⭐：这道题用带哨兵位的头结点相对来说更加简单，当然也可以用不带哨兵位的头结点，只不过用不带哨兵位的头结点更加麻烦，我们用带哨兵位的头结点做。
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode*lessHead,*lessTail,*greaterHead,*greaterTail;
        lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        
        lessTail->next=greaterTail->next=NULL;
        
        struct ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next=cur;
                lessTail=lessTail->next;
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
            }
            
            cur=cur->next;
        }
        lessTail->next=greaterHead->next;
        struct ListNode*list=lessHead->next;
        free(lessHead);
        free(greaterHead);

    return list;
    }
};
当我们程序运行时，出现了内存超限的报错，But，Why

现在让我们浅浅的分析一下一些极端情况：

1 所有值比x小

2 所有值比x大

3 比x大和小的都有，最后一个值是比x小

4 比x大和小的都有，最后一个值是比x大

分析后我们会发现问题就出现在情况3的情况，会导致程序死循环，剩余的情况大家自行分析，我就不在这里多赘述。
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode*lessHead,*lessTail,*greaterHead,*greaterTail;
        lessHead=lessTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        greaterHead=greaterTail=(struct ListNode*)malloc(sizeof(struct ListNode));
        
        lessTail->next=greaterTail->next=NULL;
        
        struct ListNode*cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lessTail->next=cur;
                lessTail=lessTail->next;
            }
            else
            {
                greaterTail->next=cur;
                greaterTail=greaterTail->next;
            }
            
            cur=cur->next;
        }
          
        lessTail->next=greaterHead->next;
        greaterTail->next=NULL;//将链表2的尾结点next置空
        
        struct ListNode*list=lessHead->next;
        free(lessHead);
        free(greaterHead);

    return list;
    }
};