[数据结构与算法]LeetCode刷题——链表OJ（历时三天，万字博客，十一道经典题，带你手撕链表）

知之愈明，则行之愈笃；行之愈笃，则知之益明。?

学完链表，我们不得刷刷题增进对链表的认识？今天博主选取十一道经典链表题，从刷题者的角度剖析重点和易错点，讲解最简单的方法，文章内附题目和题目链接，重点内容我全部用彩笔标注了，请大家放心食用。

目录

1、删除链表中等于给定值 val 的所有结点

2、反转链表

3、链表的中间结点

4、链表中倒数第k个结点

5、合并两个有序链表

6、分割链表

7、回文链表

8、环形链表

9、相交链表

10、环形链表II（升级版）

11、复制带随机指针的链表

1、删除链表中等于给定值 val 的所有结点

?上一篇文章我们讲了链表删除结点的功能，因此删除一个结点对我们来说难度不大，但是这题中可能是要删除多个结点，而且头结点很可能会被改变，更烦人的是，头结点可能一直在改变，一直被删除，导致这个问题就显得有点棘手了。那怎么处理呢？我们可以再重新定义一个头结点NewHead，保证这个头结点不会被删除，这个头结点中next指针指向就是之前的头结点，最后返回NewHead->next（也就是题目所要求返回的新的头节点）

写代码要注意的几点：

1. NewHead是我们自己手动添加的头节点，目的就是防止出现多次修改头节点的情况，因此我们要保证NewHead->val!=val，我写的代码中就直接把val+1赋值给NewHead->val，你们也可以把val+2/val-1赋值，只要不等于val就可以。
2. NewHead一定要记得初始化，除了初始化结构体成员val，还要初始化next指针，让NewHead与head节点连接起来。
3. 最后记得返回NewHead->next，而非NewHead。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* NewHead=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* cur=NewHead;
    struct ListNode* prev=NULL;
    //保证NewHead的val不为随机值，不会被删除
    NewHead->val=val+1;
    NewHead->next=head;
    while(cur!=NULL)
    {
        if(cur->val==val)
        {
            prev->next=cur->next;
        }
        else
        {
            prev=cur;
        }
        cur=cur->next;
    }
    return NewHead->next;
}

2、反转链表

?图画的有些潦草，但我觉得还是不影响它的效果

?链表跟数组不一样，反转链表并不是真的把链表的每个结点位置都反转，结点的地址都没有被改变，改变的只是每个结点所指向的内容。

讲到这，我觉得大家应该会有思路了，我们首先要用一个cur结点指针去遍历所有的结点，因为要改变cur->next，让它指向前一个结点，所以我们要用另外两个指针去记录地址，一个是prev指针，去记录前一个结点的地址，一个是next指针，去记录下一个结点的地址。

此外，需注意：

• 当cur==head时，此时没有上一个结点，而是要让head->next=NULL。
• 另外，还有种极端情况，当链表为空的时候，cur=NULL，用cur->next就有问题，如果提交代码就会出现这种情况（见下图），这段报错说明我们非法使用了空指针。我们规避这种情况就好，如果链表为空就直接返回NULL。
• 我写的while的判断条件是cur->next不为NULL，而非cur不为NULL，如果是后者，返回值就不是cur，而是prev，并且去掉循环外cur->next=prev；

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *cur=head,*next,*prev;
    prev=next=NULL;
    if(head==NULL)
      return NULL;
    while(cur->next)
    {
        next=cur->next;
        if(cur==head)
        {
            head->next=NULL;
        }
        else
        {
            cur->next=prev;
        }
        prev=cur;
        cur=next;
    }
    cur->next=prev;
    return cur;
}

?

3、链表的中间结点

?OJ链接

很多人看到这题可能第一反应就是先求出链表的长度，然后长度/2，再让指针往后走长度/2个结点，最后所到的结点就是题目要求的中间结点。

这题我加大难度，要求只允许遍历一遍链表，时间复杂度要求是O（n）。

这题需要用到快慢指针——fast和slow，fast每次走的结点是slow走的结点的两倍，这题就别问怎么得来的思路了，这就是一个方法，理解它，记住它就好了。

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

4、链表中倒数第k个结点

OJ链接 ?

混进来了一个牛客链接?(? ???ω??? ?)?，不过这题也是好题目，跟第三题差不多，也是用快慢指针，不过这题就有点小坑了。

同样，还是加大难度，只允许遍历一遍链表，时间复杂度为O（N）。

本题的思路是：fast先走k步，然后fast和slow再一起走，直到fast为NULL。

为什么要这样走呢，因为fast比slow多走k步，最后一起走，那么slow和fast的距离一直是k个结点，最后fast为空，停止运动时，slow距离NULL正好k个结点处，最后slow就到第k个结点处了。

 ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        struct ListNode *slow,*fast;
        slow=fast=pListHead;
        while(k--)
        {
            fast=fast->next;
        }
        while(fast)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }

当好像上面那个代码过不了，还说我们的代码有段错误（无处不在的段错误哈哈哈哈）。

这是因为我们只考虑了?k小于链表长度的情况，如果k大于或者等于链表长度怎么办？

我们应该在while循环里面加入一个if语句，如果fast==NULL了，我们就返回NULL。因为k还没为0，fast就为空了，那就证明k大于链表的长度。

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        struct ListNode *slow,*fast;
        slow=fast=pListHead;
        while(k--)
        {
            //k大于链表长度
            if(fast==NULL)
            {
                return NULL;
            }
            fast=fast->next;
        }
        while(fast)
        {
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

另外我还要说一嘴，刚才新加的if语句，是要放在fast=fast->next的前面（不然就会报段错误，???）当pListHead=NULL时，我们先进行fast=fast->next，此时对空指针解引用就会出现问题，也就是这非常烦人的段错误。所以这题还是有很多坑的，好好注意QAQ。

5、合并两个有序链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *cur1,*cur2,*cur;
    cur1=list1;
    cur2=list2;
    struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
    cur=head;
    head->next=NULL;
    while(cur1&&cur2)
    {
        if(cur1->val<cur2->val)
        {
          cur->next=cur1;
          cur1=cur1->next;
        }
        else
        {
          cur->next=cur2;
          cur2=cur2->next;
        }
        cur=cur->next;
    }
    if(cur1)
    {
        cur->next=cur1;
    }
    if(cur2)
    {
        cur->next=cur2;
    }
    return head->next;
}

?没错，这又是牛客的题，但是也挺好玩的，挺有意思。

题目要求我们讲小于x的结点排在其余结点之前，并且不能改变原来的数据顺序，你们是不是突然就想到我们C语言中的排序，给定一个数，比这个数小的就往前移（交换），但是这题你这样去做那会超级麻烦，先不论头结点不好写（这个可以通过哨兵结点解决），每次往前移动一个结点，我们还得记住这个结点原本的位置，原本位置处上下两个结点的位置，还要记住上一个被移动的结点的位置，保证下一次移结点后，所有的结点能够串起来，这光用文字描述起来就很复杂了，对我这种水平不高、一写代码Bug99+的小白来说，这个方法还是不适合我。那我们怎么办呢？

其实我们再仔细想想，这题就是把链表划分成两部分，一个是val小于x的结点，一个是val大于等于x的结点，我们可以在遍历链表时，把小于x的放到小结点链表里，把大于等于x的放到大结点链表里，最后再把小结点链表中最后一个结点与大结点链表里的第一个结点串起来，这样实现是不是简单多了（就一个字，强！）

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode *greatertail,*lesstail,*greaterguard,*lessguard,*cur=pHead;
        greaterguard=(struct ListNode*)malloc(sizeof(struct ListNode));
        lessguard=(struct ListNode*)malloc(sizeof(struct ListNode));
        greatertail=greaterguard;
        lesstail=lessguard;
        while(cur)
        {
            if(cur->val>=x)
            {
                greatertail->next=cur;
                greatertail=greatertail->next;
            }
            else
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
            }
            cur=cur->next;
        }
        greatertail->next=NULL;
        lesstail->next=greaterguard->next;
        return lessguard->next;
    }
};

注意：

• 倒数第二三行代码，我认为是不能互换顺序的，但是互换了也可以通过（不知道是不是牛客测试的用例太少了，还是我想错了？），我们设置了两个哨兵结点，但这两个哨兵结点的next并没有初始化，最重要的还是greaterguard->next没有初始化，如果这个链表是空链表，我们最后返回的应该是空，lesstail此时==lessguard，greatertail==greaterguard，当我们把greatertai->next=NULL放到前面正好可以满足这种极端情况。
• 倒数第三行代码为什么要写greatertai->next=NULL？因为链表的最后一个结点的next指向NULL。这个特别容易被忽视。

7、回文链表

?力扣

什么是回文链表，链表对称就被称作回文链表。 对称，顾名思义，就是以链表的中心为对称轴，如果两边的结点的val都相等，那么说明这个链表就是对称的。

判断条件我们都已经清楚了，这题的难度就在于链表是有方向的，怎么一一比较对称的结点呢？

首先，我们要找到链表的中心结点，如果是链表有奇数个结点，就选那个唯一的中间结点，如果链表有偶数个结点，有两个中间结点，那么就选择第二个中间结点。然后，我们在第二题学习了反转链表，我们就反转以中间结点为头结点的链表，最后函数的返回值为反转后新的头结点。我举个例子，反转后的链表整体如下：

?然后分别从head和head1处开始比较，如果中间有结点的val不相等，那么就返回false，如果最后跳出循环了，那么就返回true。

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *cur=head,*next,*prev;
    prev=next=NULL;
    if(head==NULL)
     return NULL;
    while(cur)
    {
        next=cur->next;
        if(cur==head)
        {
            head->next=NULL;
        }
        else
        {
            cur->next=prev;
        }
        prev=cur;
        cur=next;
    }
    return prev;
}
bool isPalindrome(struct ListNode* head){
    struct ListNode* fast=head,*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    struct ListNode* head1=reverseList(slow);
    while(head&&head1)
    {
        if(head->val==head1->val)
        {
            head=head->next;
            head1=head1->next;
        }
        else
        {
            return false;
        }
    }
    return true;
}

有人可能会有疑惑：万一最后跳出循环是因为head或者head1为NULL，并不一定两个都为NULL，那就证明不了这个链表是回文结构了呀？（我当时写完代码，真的就这样思考过）

我们想想，反转链表是反转以中间结点为起始结点的链表，那么head和head1两段链表肯定是对称的，如果有一方为空，另一方肯定也为空。（为机智的我点个赞！！！o(￣▽￣)ｄ）

8、环形链表

?OJ链接

什么是环形链表，环形链表的尾部结点不指向NULL，而是指向链表中的任意一个结点，整个链表一直没有结束的标志。

如何去判断环形链表呢？我们可以先想想如何判断整个链表绝对不会是环形链表，用一个指针去遍历整个链表，如果这个指针最后变成了空指针，此时链表就走到末尾了，这显然不是环形链表。那如果用快慢指针，一个走的快，一次走两步，一个走的慢，一次走一步，最后快的追上了慢的，那么就证明这是一个环形链表。并且只要这是环形链表，那么就一定能追上，我证明一下：

上代码：

bool hasCycle(struct ListNode *head) {
    struct ListNode*fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

?注意：

• while循环的判断条件里要写fast&&fast->next均不为空，为什么要写fast->next不为空呢，因为fast一次走两步，如果fast->next为NULL，进行fast=fast->next->next的操作就是对空指针的解引用了，会出现段错误。
• 这个错误是我在写代码的时候犯的，我不知道大家会不会错，但我还是想说一下，如果while循环代码写成如下，能通过吗？

  while(fast&&fast->next)
      {
          if(fast!=slow)
          {
              fast=fast->next->next;
              slow=slow->next;
          }
          else
          {
              return true;
          }
      }

  最后是不能通过，因为fast和slow最开始就是相等的，都等于head，那么只要fast和fast->next不为空，第一次进来的时候，就满足else条件，然后返回true，但实际不一定是true。

那如果快指针走三步，慢指针走一步，一定相遇吗？

答案是不一定：

9、相交链表

?OJ链接

这题主要是学会思路，思路对了就不会犯什么错误了，代码思想我用注释标注出来了。?

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //找尾结点，尾结点如果相等，那么肯定就相交
    struct ListNode* cur1=headA,*cur2=headB;
    int len1=1,len2=1;
    while(cur1->next)
    {
        cur1=cur1->next;
        len1++;
    }
    while(cur2->next)
    {
        cur2=cur2->next;
        len2++;
    }
    //尾结点都不相等，那么肯定不相交
    if(cur2!=cur1)
    {
        return NULL;
    }
    int gap=fabs(len2-len1);
    struct ListNode* larger=headA,*lesser=headB;
    if(len2>len1)
    {
        larger=headB;
        lesser=headA;
    }
    //让结点数多的链表指针先走gap步
    while(gap--)
    {
        larger=larger->next;
    }
    //同时走，直到二者相等
    while(larger!=lesser)
    {
        larger=larger->next;
        lesser=lesser->next;
    }
    //二者相等，可能是因为到了相交结点，也可能是到了链表尾部，最后均为NULL
    return larger;
}

10、环形链表II（升级版）?

?思路一（公式法）：

这题真的有点困难，我们需要通过推导公式找到思路

?上代码：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*meet=NULL,*cur,*slow,*fast;
    slow=fast=cur=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            meet=slow;
            break;
        }
    }
    if(fast==NULL||fast->next==NULL)
       return NULL;
    while(meet!=cur)
    {
        meet=meet->next;
        cur=cur->next;
    }
    return meet;
}

思路二（找相交结点）：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //找尾结点，尾结点如果相等，那么肯定就相交
    struct ListNode* cur1=headA,*cur2=headB;
    int len1=1,len2=1;
    while(cur1->next)
    {
        cur1=cur1->next;
        len1++;
    }
    while(cur2->next)
    {
        cur2=cur2->next;
        len2++;
    }
    //尾结点都不相等，那么肯定不相交
    if(cur2!=cur1)
    {
        return NULL;
    }
    int gap=fabs(len2-len1);
    struct ListNode* larger=headA,*lesser=headB;
    if(len2>len1)
    {
        larger=headB;
        lesser=headA;
    }
    //让结点数多的链表指针先走gap步
    while(gap--)
    {
        larger=larger->next;
    }
    //同时走，直到二者相等
    while(larger!=lesser)
    {
        larger=larger->next;
        lesser=lesser->next;
    }
    //二者相等，可能是因为到了相交结点，也可能是到了链表尾部，最后均为NULL
    return larger;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*meet=NULL,*cur,*slow,*fast;
    slow=fast=cur=head;
    //找快慢指针相遇点
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        {
            meet=slow;
            //断开链表
            struct ListNode*next,*NEXT;
            next=NEXT=meet->next;
            meet->next=NULL;
            struct ListNode* GetInterNode=getIntersectionNode(next,head);
            //因为不能破坏链表结构，所以要复原链表
            meet->next=NEXT;
            return GetInterNode;
        }
    }
    return NULL;
}

11、复制带随机指针的链表

?OJ链接

这个链表跟我之前学过的链表有些不同，之前学的链表只有两个成员，一个记录value，一个记录下一个结点的地址，而本题的结点有三个成员，外加了一个random指针，随意指向链表中的一个结点。本题的意思是让我们复制出一个与原链表一模一样的新链表，最棘手还是的random指针的赋值。

方法一（暴力求解）：

这个方法时间复杂度为O（N^2），时间复杂度还是挺大的，效率有点低，但是思路简单啊（好适合我这种非大佬小人物用啊）

struct Node* copyRandomList(struct Node* head) {
	struct Node* newhead=(struct Node*)malloc(sizeof(struct Node)),*cur,*cur1,*cur3,*cur4;
    if(head==NULL)
    {
        return NULL;
    }
    newhead->val=head->val;
    cur=head->next;
    cur1=newhead;
    //构建复制的新链表
    while(cur)
    {
        struct Node* Node=(struct Node*)malloc(sizeof(struct Node));
        Node->val=cur->val;
        cur1->next=Node;
        cur1=cur1->next;
        cur=cur->next;
    }
    cur1->next=NULL;
    //复制random
    cur1=newhead;
    cur=head;
    while(cur)
    {
        if(cur->random==NULL)
        {
            cur1->random=NULL;
        }
        else
        {
            cur3=head;
            cur4=newhead;
            //这里就开始复制random了
            while(cur3!=cur->random)
            {
                cur3=cur3->next;
                cur4=cur4->next;
            }
            cur1->random=cur4;
        }
        cur1=cur1->next;
        cur=cur->next;
    }
    return newhead;
}

这里我提醒一下， 赋值random时while循环的条件是cur3!=cur->random，而不是cur4->val!=cur->random->val，万一链表中有两个结点存储的value是一样的就错了！！！！！

方法二（大佬用的方法）：

这个方法有点难想，但是效率高，时间复杂度为O(N)（咸鱼都能翻身，我们也不能堕落，得学一点高级的方法！！！）

第一步：先创建新节点，让每个新结点的位置满足以下情况，并且让每个复制的结点的value都等于原结点的value。

第二步：复制random，分成两种情况，第一种情况，原结点的random指向NULL，那复制的结点的random也指向NULL。第二种情况，原结点的random指向非NULL，复制的节点的random指向原结点random的下一个结点。（注意：迭代的时候是跳一个节点迭代）

第三步：断开原链表和复制链表。这个要分为是头结点和非头结点的情况，这个大家自行画图去理解，思路不是很难，注意细节就ok。

struct Node* copyRandomList(struct Node* head) {
	struct Node *cur,*newnode,*next=NULL;
    cur=head;
    //创建新结点，赋值value
    while(cur)
    {
        struct Node*newnode=(struct Node*)malloc(sizeof(struct Node));
        next=cur->next;
        cur->next=newnode;
        newnode->next=next;
        newnode->val=cur->val;
        cur=next;
    }
    //赋值random
    cur=head;
    while(cur)
    {
        if(cur->random==NULL)
        {
            cur->next->random=NULL;
        }
        else
        {
            cur->next->random=cur->random->next;
        }
        //迭代
        cur=cur->next->next;
    }
    //断开链表变成两个链表
    struct Node* newhead=NULL,*newtail=NULL;
    cur=head;
    while(cur)
    {
        next=cur->next->next;
        if(newtail==NULL)
        {
            newhead=newtail=cur->next;
        }
        else
        {
            newtail->next=cur->next;
            newtail=newtail->next;
        }
        //恢复
        cur->next=next;
        //迭代
        cur=cur->next;
    }
    return newhead;
}

LeetCode上还有好多关于链表的题目，大家可以自行刷题，我这篇文章选了最经典的十一道题，全部学会，你对链表的理解一定能上升一个台阶！

数据结构很难，我们要继续努力学习它呀！

好了，喜欢我的文章，就给我点个赞&&点个关注再走吧 ！！

?