目录

一：前言

二：简单题目

(1)移除链表元素

(2)反转链表

(3)找链表的中间结点

(4)输入一个链表，输出该链表中倒数第k个结点

(5)合并两个有序链表

(6)相交链表

(7)判断链表是否带环

三：较难题目

(1)链表分割

(2)判断链表是否为回文结构

(3)找到成环链表的入环结点

(4)复制带随机指针的链表

一：前言

这一部分链表的OJ的题目适用于已经掌握链表基础的同学。

如果有对链表基础功能实现有问题的同学可以看这里：

https://blog.csdn.net/2301_76269963/article/details/129586021?spm=1001.2014.3001.5501

二：简单题目

(1)移除链表元素

链接：https://leetcode.cn/problems/remove-linked-list-elements/description/

题目要求：

基础思路：

【1】特殊情况：链表为空直接返回NULL。

【2】使用一个cur指针遍历整个链表。

【3】涉及到释放结点，要提前用next指针记录下一个位置。

【4】 用prev记录要删除的结点的前一个结点，保证链表连通。

【5】如果要删除，prev不变；不用删除的话prev，next，cur都要迭代。

【6】如果删除的是头结点，头结点要进行迭代。

代码：

struct ListNode* removeElements(struct ListNode* head, int val) {     //如果链表为空，直接返回NULL。    if (head == NULL)    {        return head;    }    //当前结点    struct ListNode* cur = head;    //记录下一个结点    struct ListNode* next = head->next;  //记录原结点    struct ListNode* prev = head;    while (cur)    {  //如果找到要删除的结点        if ((cur->val) == val)        {//如果释放的是头结点            if (cur == head)            {                free(cur);                head = next;                cur = next;            }//释放的不是头结点            else            {                free(cur);                prev->next = next;            }        }//没找到进行prev迭代        else        {            prev = cur;        }        //迭代，要考虑next已经为空的情况        cur = next;        if (next)            next = next->next;    }    //返回头结点    return head;}

(2)反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/description/

题目要求：

基础思路：

【1】建立一个新的头。

【2】将原链表中的元素一个个拿下来。

【3】用prev记录新链表前一个结点，然后让新拿下来的结点指向prev。

图解：

代码：

struct listnode* reverselist(struct listnode* head){//一个个拿出来链接struct listnode* newnode = head;   //记录前一个指针struct listnode* prev = NULL;while (head){     //head指向后一个结点    head = head->next;     //改变结点指向    newnode->next = prev;    prev = newnode;     //newnode要作为新的头结点，不能指空    if (head)        newnode = head;}return newnode;}

(3)找链表的中间结点

链接：https://leetcode.cn/problems/middle-of-the-linked-list/description/

题目要求：

基础思路：

【1】设置一个慢指针slow和一个快指针fast。

【2】慢指针slow走一步，快指针fast走两步。

【3】当fast为空或者fast->next（避免对空指针解引用）为空就结束循环。

图解：

代码：

struct ListNode* middleNode(struct ListNode* head){  //慢指针struct ListNode* slow = head;   //快指针struct ListNode* fast = head;while (fast){   //如果是偶数个结点，fast为最后一个时应该直接跳出if (fast->next == NULL)break;fast = fast->next->next;slow = slow->next;} //返回慢结点return slow;}

(4)输入一个链表，输出该链表中倒数第k个结点

链接：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

题目要求：

基础思路：

【1】考虑特殊情况：链表为空，返回空；给的k值大于链表结点数，返回空。

【2】还是利用快慢指针，快指针先走k步，然后快慢指针相同速度走，直到快指针为空，此时慢指针就是要求的结点。

代码：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {    //如果为空链表直接返回空 if (pListHead == NULL)return NULL;struct ListNode* slow = pListHead;struct ListNode* fast = pListHead; //快指针先走k步for (int i = 0; i next;} //慢指针会一直落后k个结点while (fast){    fast = fast->next;    slow = slow->next;} //返回慢指针return slow;}

(5)合并两个有序链表

链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目要求：

基础思路：

【1】考虑特殊情况：其中一个链表为空返回另一个链表。

【2】设置一个新头newhead和新尾newtail。

【3】依次比较链表结点，小的拿下来作为新尾。（相同情况拿第一个链表）

【4】其中一个链表走空结束循环，将没走完的链表的剩余结点链接到新链表后面。

图解：

代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){//设置一个新的头和新的尾struct ListNode* newhead = NULL, * newtail = NULL;//如果其中一个链表为空，返回另一个链表if (list1 == NULL)return list2;if (list2 == NULL)return list1;//如果第一个链表的结点数据大于第二个链表结点数据，//那第二个链表的头结点作为新头，反之第一个链表头结点作为新头if (list1->val >= list2->val){newhead = newtail = list2;list2 = list2->next;}else{newhead = newtail = list1;list1 = list1->next;}//一直循环，直到一边为空while (list1 && list2){//如果第一个链表的结点数据小，把这个结点接到新链表后面//然后进行迭代，指向下一个结点if (list1->val val){newtail->next = list1;newtail = list1;list1 = list1->next;}//如果第二个链表的结点数据小，把这个结点接到新链表后面//然后进行迭代，指向下一个结点else{ newtail->next = list2; newtail = list2; list2 = list2->next; }}//将没走到的链表的后续结点链接到新链表后面if (list1)newtail->next = list1;elsenewtail->next = list2;//返回新链表头return newhead;}

(6)相交链表

链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

题目要求：

• 这个题目最好想到的方法就是暴力求解，将其中一个链表的每一个结点与另一个链表的每一个结点比较，如果存储的地址相同，说明下一个结点是相交结点，这样就利用了双重循环，时间复杂度到达了O(n^2),我运行的时候没通过，下面我们介绍一种时间复杂度为O（n）,思路相对简单的方法。

基础思路：

【1】考虑特殊情况：其中一个链表为空，返回空。

【2】易知当两个非空链表相交时，两个链表的尾结点一定是相交结点，我们可以利用尾结点，判断两者是否相交。

【3】在找尾结点的同时计算两个链表的步长，计算距离差距gap，让长链表先走gap步，然后两个链表一起走，直到找到地址相同的结点（即交点）。

图解：

代码：

struct listnode* getintersectionnode(struct listnode* heada, struct listnode* headb) {    //计算长度    int lengtha = 1;    int lengthb = 1;    //如果其中一个为空，返回空    if (heada == null || headb == null)        return null;    //找两个链表的尾结点并计算长度    struct listnode* taila = heada;    struct listnode* tailb = headb;    while (taila->next)    {        taila = taila->next;        lengtha++;    }    while (tailb->next)    {        tailb = tailb->next;        lengthb++;    }    //判断相交    if (taila != tailb)    {        return null;    }    //计算相差步长，abs函数可以算两数的绝对值    int gap = abs(lengthb - lengtha);    //设B链表长，A链表短    struct listnode* longlist = headb;    struct listnode* shortlist = heada;    //如果A链表长，改变值    if (lengtha > lengthb)    {        shortlist = headb;        longlist = heada;    }    //长链表先走gap步    while (gap--)    {        longlist = longlist->next;    }    //循环求两个链表交点    while (longlist != shortlist)    {        longlist = longlist->next;        shortlist = shortlist->next;    }    //返回交点    return longlist;}

(7)判断链表是否带环

链接：https://leetcode.cn/problems/linked-list-cycle/description/

题目要求：

•在讲述基础思路前，我想先进行一个数学推导，如果有一个环形赛道，其中一个人A以速度2m/s跑，一个人B以速度1m/s跑,请问A是否能追上B？

很明显A一定会追上B，就像链表成环一样，两步走的一方一定会在环内部追上一步走的一方（链表的环长一定是正整数）。

图解：

基础思路：

【1】考虑特殊情况：链表为空，返回空。

【2】设置一个慢指针slow和快指针fast,慢走一步，快走两步。

【3】如果fast或者fast->next为空,说明链表不成环。

【4】如果成环，fast一定会追上slow，追上了返回true。

图解：

代码：

bool hasCycle(struct ListNode* head){struct ListNode* slow = head, * fast = head;//如果链表为空，返回falseif (head == NULL)return false;while (fast->next){//慢指针走一步，快走两步slow = slow->next;fast = fast->next->next;//如果走完直接为空，返回falseif (fast == NULL)return false;//如果fast追到slow,说明链表成环，返回true。if (fast == slow)return true;}//如果fast->next为空，链表不成环，返回false。return false;}

三：较难题目

(1)链表分割

链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

题目要求：

基础思路：

【1】设计一个cur指针遍历链表。

【2】将链表分割成两个链表，数据小于x的结点合成一个链表（简称小链表），数据大于x的合成一个链表（简称大链表）。

【3】考虑特殊情况：链表为空返回空，分割处理后如果其中一个链表为空，返回另一个链表。

【4】分割结束后小链表的尾要和大链表的头链接，大链表的尾要指向空。

图解：

代码：

struct listnode* partition(struct listnode* head, int x) {  //如果给的链表为空，我们直接返回空    if (head == NULL)            return NULL;    //用来遍历整个链表    struct listnode* cur = head;    //小于x的链表    struct listnode* lesshead = NULL;    struct listnode* lesstail = NULL;    //大于等于x的链表    struct listnode* biggerhead = NULL;    struct listnode* biggertail = NULL;    //遍历整个链表    while (cur)    {        if (cur->val next = cur;                lesstail = cur;            }        }        else        {            //小于x的链表的第一个结点的插入            if (biggerhead == NULL)            {                biggerhead = biggertail = cur;            }            else            {  //让原来的尾指向新尾                biggertail->next = cur;                biggertail = cur;            }        }        //cur迭代        cur = cur->next;    }    //小链表的尾指向大链表头，大链表尾指空。    //如果其中一个链表为空，不对其解引用    if (lesstail != NULL)        lesstail->next = biggerhead;    if (biggertail != NULL)        biggertail->next = NULL;    //如果没有元素小于x,返回大的链表    if (lesstail == NULL)        return biggerhead;    //如果没有元素大于x,返回小的链表    else        return lesshead;}

(2)判断链表是否为回文结构

链接：https://leetcode.cn/problems/aMhZSa/

题目要求：

基础思路：

【1】先找到中间的结点。（前面有）

【2】反转中间结点后的链表。（前面有）

【3】遍历两个链表，依次比较，有不同返回false。

【4】循环结束条件为两个链表任意一个走到空。

图解：

代码：

//判断链表是否为回文//找中间结点struct ListNode* middleNode(struct ListNode* head) {struct ListNode* slow = head;struct ListNode* fast = head;while (fast){if (fast->next == NULL)break;fast = fast->next->next;slow = slow->next;}return slow;}//进行反转struct ListNode* reverseList(struct ListNode* phead){struct ListNode* newnode = phead;//记录前一个指针struct ListNode* prev = NULL;while (phead){//head指向后一个结点phead = phead->next;//改变结点指向newnode->next = prev;prev = newnode;//newnode要作为新的头结点，不能指空if (phead)newnode = phead;}return newnode;}//判断是否为回文bool isPalindrome(struct ListNode* head) {//找中间struct ListNode* mid = middleNode(head);//反转struct ListNode* rHead = reverseList(mid);//前半段struct ListNode* cur1 = head;//后半段struct ListNode* curA = rHead;  //一个个判断，不同直接返回falsewhile (cur1 && curA){if (cur1->val != curA->val){return false;}else{//如果相同，迭代cur1 = cur1->next;curA = curA->next;}}  //全部相同，返回true。return true;}

(3)找到成环链表的入环结点

链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

题目要求：

题目的两种思路：

1.相遇后断开

基础思路：

【1】设计快慢指针，快走两步，慢走一步，找到第一次相遇的结点（简称meet）。

【2】在这个结点处断开，meet指向空，meet原来的下一个结点作为新链表的头。

【3】题目就转换为了求两个链表的交点。

图解：

代码：

//第二解法，断开找交点struct ListNode* detectCycle(struct ListNode* head){    struct ListNode* slow = head, * fast = head;    while (fast && fast->next)    {        slow = slow->next;        fast = fast->next->next;        //相遇        if (fast == slow)        {            struct ListNode* meet = fast;            //第二个链表的头            struct ListNode* newhead = fast->next;            fast->next = NULL;            //找到交点            struct ListNode* headTail = head;            struct ListNode* newheadTail = newhead;            //计算长度            int len = 0;            int newLen = 0;            while (headTail)            {                headTail = headTail->next;                len++;            }            while (newheadTail)            {                newheadTail = newheadTail->next;                newLen++;            }            //计算长度差距            int gap = abs(newLen - len);            struct ListNode* longList = newhead;            struct ListNode* shortList = head;            if (len > newLen)            {                longList = head;                shortList = newhead;            }            //长链表先走gap步            while (gap--)            {                longList = longList->next;            }            while (longList != shortList)            {                longList = longList->next;                shortList = shortList->next;            }            //返回交点            return longList;        }    }    //走到空返回NULL    return NULL;}

2.数学公式法（更加简洁）

基础思路：

【1】先进行数学推导。

【2】将公式转换成代码。

推导：

代码：

//判断是否成环并且找到入环点struct ListNode* detectCycle(struct ListNode* head) {//判断是否有环struct ListNode* fast = head, * slow = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;//相遇if (fast == slow){//公式法struct ListNode* meet = slow;while (head != meet){head = head->next;meet = meet->next;}return meet;}}//没有成环，返回空。return NULL;}

(4)复制带随机指针的链表

链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

题目要求：

基础思路：

【1】考虑特殊情况：链表为空，返回空。

【2】我们可以依次复制链表中的结点并将它们放在原链表结点之后。

图解：

★★★链接之后我们可以发现一个非常神奇的规律，那就是除了random指向NULL的情况，其它新生成结点的random都是它前一个结点的random的next。

【3】根据规律复制random

【4】合成新链表，恢复原链表。

图解：

代码：

struct node* copyrandomlist(struct node* head) {    //如果链表为空。返回空    if (head == NULL)        return NULL;    //复制加链接    struct node* cur = head;    while (cur)    {        //生成新结点        struct node* copy = (struct node*)malloc(sizeof(struct node));        //复制数据域        copy->val = cur->val;        //复制指针域        copy->next = cur->next;        //链接两个链表        cur->next = copy;        //迭代        cur = copy->next;    }    //复制random    cur = head;    while (cur)    {        struct node* copy = cur->next;        //cur->random为空的情况单独处理        if (cur->random == NULL)            copy->random = NULL;        else        {            copy->random = cur->random->next;        }        //迭代        cur = copy->next;    }    //切割复原    cur = head;    //新链表的头和尾    struct node* copyhead = cur->next;    struct node* copytail = cur->next;    while (cur != NULL)    {        //恢复原链表结构        cur->next = copytail->next;        //cur迭代        cur = cur->next;        //如果cur为空，不进行迭代        if (cur )        {            //旧尾指向新尾            copytail->next = cur->next;            //迭代            copytail = copytail->next;        }    }    //返回新链表的头    return copyhead;}