链表OJ题目合集第一弹：移除元素，反转链表，中间结点，倒数第k个结点，合并有序链表，回文结构，相交链表判断。(C语言版，有详细解析、图示和链接)

目录

前言

1. 移除链表元素

（1）题目及示例

（2）解析

（3）代码

2. 反转链表

（1）题目及示例

（2）题目解析及思路

3.链表的中间结点

（1）题目及示例

（2）题目解析及思路

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

（1）题目及示例

（2）题目解析及思路

5.合并两个有序链表

（1）题目及示例

（2）题目解析及思路

6.链表的回文结构

（1）题目及测试样例

（2）题目解析及思路

7.相交链表

（1）题目及示例

（2）题目解析及思路

总结

---

前言

上篇文章是有关于两个较常用链表的结构的实现。实现完链表过后，我们还需要会熟练运用链表这种数据结构，所以这里将会有十道链表OJ题目，本篇文章将会先分析解决七道题目，剩下三道留在下一篇文章。每道题都题目后都有链接，还会有大量的图示，帮助你理解题目解法，附上解题代码。

---

1. 移除链表元素

（1）题目及示例

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。链接--力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

 //题目结构题定义如下
 struct ListNode 
{
    int val;
    struct ListNode *next;
 };

 注意：之后题目若没有详细说明，都是以上面单链表结构体为准！！！

示例1：

输入：head = [1，2，6，3，4，5，6]，val = 6

输出：[1，2，3，4，5]

示例2：

输入：head = [ ]，val = 1

输出：[ ]

示例3：

输入：head = [7，7，7，7]，val = 7

输出：[ ]

（2）解析

从题目和示例来看，就是去除链表中存储数据相同的结点时，跟单链表的删除操作十分相似。需要注意的是特殊情况，链表为空的时候直接返回空链表即可。在删除的过程中要分两种情况，分别是头部删除和中间删除，这是因为改题目要求返回新的头结点，中间的删除不会影响头结点的指向。

下面分析这两步操作，在执行前，我会定义prev和cur这两个指针，prev指向空指针，cur指向头结点。prev指向的是cur指针的前一个结点，但是一开始cur指向头结点，所以指向空。

• 头部删除，假设val = 1。

• 中间删除，假设val = 3。

• 迭代往后走，是中间删除这一步的后续。

（3）代码

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if (cur->val == val)
        {
            //1.头部珊除
            //2.中间删除
            if (cur == head)
            {
                head = cur->next;
                free(cur);
                cur = head;
            }
            else
            {   //删除
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {   //往后走
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

2. 反转链表

（1）题目及示例

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

示例1：

输入：head = [ 1，2，3，4，5 ]

输出：[ 5，4，3，2，1 ]

示例2：

输入：head = [ 1，2，3，4，5 ]

输出：[ 5，4，3，2，1 ]

示例3：

输入：head = [  ]

输出：[  ]

（2）题目解析及思路

这个题目意思比较明显，我们需要把链表整个指向反转过来。有以下几种思路：

1. 正常来说，最平常的思路就是自己开辟与题目示例所给相同的个数的结点，并先遍历链表找到尾结点，依次寻找前面的结点，但是十分麻烦。倘若有五个节点需要遍历4+3+2+1+0次次，时间复杂度相当于O(N^2)，空间复杂度为O(N)。

2. 在第一种做法的基础上，进一步优化，还是开辟示例所给相同个数的结点，但是这次我们只需要遍历一次链表即可。我们需要三个指针，是cur，newCur，newPrev，分别指向原链表，新链表。

• 一开始cur指向原链表的头结点，newCur，newPrev都指向空。
• 当开辟第一个结点时，newCur指向它，将其next指针指向空，并让newCur的val赋值为cur的val值，cur指向下一个结点。
• 当开辟第二个结点时，newCur指向它，newPrev指向前一个结点，即第二个结点。让newCur的next指针指向第一个结点，也就是现在的newPrev，然后赋值，cur指向下一个结点。
• 中间不断进行上述操作……
• 当cur指向原链表最后一个结点的时候，进行赋值，修改指针指向，cur将会继续往后走，此时cur为NULL空指针。因此写一个while循环，判断条件就是cur指针，当它为空时循环结束，返回新链表头结点newCur。

这个做法只需遍历链表一次，时间复杂度为O(N)，空间复杂度还是O(N)。代码如下：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newCur= NULL;
    struct ListNode* newPrev= NULL;
    while(cur)
    {
        newCur = (struct ListNode*)malloc(sizeof(struct ListNode));
        if (cur == head)
        {   //赋值
            newCur->val = cur->val;
            newCur->next = NULL;
            //迭代往后
            newPrev = newCur;
            cur = cur->next;
        }
        else
        {   //赋值
            newCur->val = cur->val;
            newCur->next = newPrev;
            //迭代往后
            newPrev = newCur;
            cur = cur->next;
        }
    }
    return newCur;
}

3. 不过大家可以仔细想想，既然我们创建新链表的时候可以反转，为什么不直接在原链表进行反转。这就是此题的最优解，在空间上，只需要创建几个指针变量，空间复杂度为O(1)，在时间上，只需要遍历一次链表即可，时间复杂度为O(N)。

在开始反转前，需要创建三个指针变量，cur，newhead和next，其中next是放在while循环中创建的指针变量。cur先指向头结点，newhead指向空指针。

• 假设一个链表head = [ 1，2，3，4 ]，一开始情况如下图，next指针指向的是cur的下一个结点。

•  把cur的next指针指向newhead，即把第一个结点指向空，然后迭代往后走，next指针的作用就体现出来了。newhead指向cur的位置，cur指向next的位置。

• 在下一次操作中，next指向cur下一个结点的位置，在改变第二个结点的指向。

• 接下来重复上述操作，如图所示

• 当cur指针到达最后一个结点的时候，再次改变指针指向。而cur指向空，newhead指向最后一个结点时，完成反转链表，所以while循环判断是cur不为空时，最后返回newhead指针就行。

代码如下：

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
 
        //迭代往后走
        cur = next;
    }
    return newhead;
}

3.链表的中间结点

（1）题目及示例

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

示例1：

输入：head = [ 1，2，3，4，5 ]

输出：[ 3，4，5 ]

解释：链表只有一个中间结点，值为3.

示例2：

输入：head = [ 1，2，3，4，5 ]

输出：[ 3，4，5 ]

解释：链表只有两个中间结点，值分别为3和4，返回第二个结点。

（2）题目解析及思路

寻找中间结点需要分奇数和偶数两种情况。

• 如果是奇数，可以直接找中间结点
• 如果是偶数，中间结点有两个，根据题目要求，返回第二个中间结点，这里是要注意的地方。

解法一：

正常来说，因为单链表不知道结点个数，需要利用一个指针变量遍历整个链表，记下链表长度，然后再次从头节点开始，让指针指向链表长度的一半。总的来说，在时间消耗上，如果有N个结点，需要执行N + N / 2 + 1次。

解法二：

那有没有更好的解法呢？那就得请出快慢指针了，在第一种解法上进一步优化，只需遍历一遍链表。怎么做呢？快慢指针顾名思义有两个指针，一个走的快，一个走得慢。

• 假设是奇数个结点的链表，快指针走两步，慢指针走一步，以示例一为例，当slow指针走到中间结点时，fast指针刚好走到最后一个结点。

• 如果是偶数结点，以示例二为例，下列图示第二张直接从第一个中间结点3开始。当走到第二个中间结点时，fast指针指向空。

综上所述，while循环结束条件是fast指针为空或者fast的next指针为空。

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;
}

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

（1）题目及示例

输入一个链表，输出该链表中倒数第k个结点。链接：链表中倒数第k个结点_牛客题霸_牛客网

示例1：

输入：1， [ 1，2，3，4，5 ]

输出：[ 5 ]

解释：倒数第一个结点是5，返回5字后的链表

（2）题目解析及思路

这道题跟中间结点类似，只不过是求倒数第k个结点，下面我提供两种思路

解法一：

正常来说，大家首先想到的应该是遍历知道链表节点个数，然后再从头结点开始，走n-k步。在时间消耗上，最坏的情况是要走2 * n步。

解法二：

这里会使用快慢指针，但与找中间结点不同的是，这次是fast指针先走，然后slow指针和fast指针都走一步。为什么是这样子呢？我们以链表 [ 1，2，3，4，5 ]，K = 2为例。

• 上图我们可以发现倒数第K个结点与空结点相差2步，我们可以让slow指针和fast指针相差K步，然后每次都走一步直到结束。现在我们让fast指针先行K步。

• 然后，slow指针和fast指针同时都走一步。

所以说在时间消耗上，只需要遍历一次链表，是第一种解法的优化。我们已经分析完了过程，代码怎么写呢？首先用一个while循环让fast指针先走K步。其次，再用while循环让两个指针一起走，结束条件是fast的指针为空。不过得注意的是，如果是空链表或者k小于零的情况，直接返回空指针。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    if (pListHead == NULL || k <= 0)
        return NULL;
    struct ListNode* slow, *fast;
    slow = fast = pListHead;
    while(k--)//先走K步
    {
        if (fast == NULL)
            return NULL;
        fast = fast->next;
    }
 
    while(fast != NULL)//同时走一步
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

5.合并两个有序链表

（1）题目及示例

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

struct ListNode* mergeTwoLists
(struct ListNode* list1, 
struct ListNode* list2) {
}

示例1：

输入：l1 = [ 1，2，4 ]，l2 = [ 1，3，4 ]

输出：[ 1，1，2， 3，4，4 ]

示例2：

输入：l1 = [  ]，l2 = [  ]

输出：[  ]

示例3：

输入：l1 = [  ]，l2 = [ 0 ]

输出：[ 0 ]

（2）题目解析及思路

这道题有递归和迭代两种方式，这里只详解迭代的方式。迭代思路还是比较好想的，难的是代码实现。思路就是链表一和链表二从第一个结点开始比较，较小的结点就成为新链表的结点，较大的继续跟下一个结点比较，直到所有结点比较完。在写代码上，有两种形式，就是带不带哨兵位的结点。自己创建一个指针head表示新链表的头，还有一个tail指针，为插入后续节点服务，将这两个指针都赋值为空指针。

• 如果不带哨兵位结点，需要注意第一次比较，不论是第一个链表还是第二个链表结点成为新链表的头，都要单独处理，head和tail都指向list1的头结点。其他的情况，让tail的next指针指向较小结点，并且每步的较小结点的链表需要指向下一个结点。

• 此时list1已经走到tail指针的后面，就是空指针，我们写一个while循环结束的条件就是其中一个题目给的链表指针走到空指针。最后我们要加上一个判断，判断哪个链表为空，就将tail的next指针指向现在list1。

在这之前还要判断链表有没有空的情况。代码如下：

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 (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指针为空的情况。并且还要释放掉我们动态开辟的结点，返回head的下一个结点。

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;
 
    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;
        }
    }
    if (list1)
    {
        tail->next = list1;
    }
    if (list2)
    {
        tail->next = list2;
    }
 
    struct ListNode* list = head->next;
    free(head);
    return list;
}

6.链表的回文结构

（1）题目及测试样例

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。链接：链表的回文结构_牛客题霸_牛客网

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
    }
};

这道题在牛客网中没有提供C语言版，有C++函数，可以直接在此函数内部写C语言版代码。因为C++兼容C语言。

测试样例：

输入：A = [ 1->2->2->1 ]

输出：true

（2）题目解析及思路

这道题目要判断是否为回文结构，我们可以观察回文链表，发现回文链表从中间结点断开，两边是对称的，那我们可以找到中间结点，并把中间结点之后的链表逆置，再进行比较存储的整型值。因此，之前写的两道题反转链表和找中间结点就可以派上用场了。不过得注意奇数偶数的情况。

• 如果是奇数个结点，利用之前写的寻找中间结点刚好只有一个。

•  如果是偶数个结点，中间结点有两个，之前的寻找中间结点函数是找到第二个中间结点。

要反转中间结点后的链表，有的人会直接断开，就像下面图例的情况，如果是偶数个结点，从头开始比较，到空指针的时候结束了。如果是奇数个结点，断开的时候会多出一个中间结点，只要其中一个链表走到空指针就结束，所以比较判断结束条件是其中一个链表为空。但是反转链表后，还需要断开链表，比较麻烦，我们可以看看不断开的情况。

如下图所示，这就是不断开的情况。如果是奇数个结点，从两边开始比较，最后都会走向空指针。如果是偶数个结点，从两边开始比较，其中一个会先走到空指针，就结束对比的过程。

你可以把寻找中间结点函数和反转链表函数再重新写一遍，也可以直接借用，再进行比较。

//寻找中间结点
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;
}
 
//反转链表
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = nullptr;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        //迭代往后走
        cur = next;
    }
    return newhead;
}
 
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {   //找到中间结点
        struct ListNode* mid = middleNode(A);
        //中间结点的头
        struct ListNode* rHead = reverseList(mid);
        //原链表的左右结点
        struct ListNode* curLeft = A;
        struct ListNode* curRight = rHead;
        while (curLeft && curRight)
        {
            if (curLeft->val != curRight->val)
            {
                return false;
            }
            else 
            {
                curLeft = curLeft->next;
                curRight = curRight->next;
            }
        }
        return true;
    }
};

7.相交链表

（1）题目及示例

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。

示例1：

输入：intersectVal = 8, listA = [ 4，1，8，4，5 ]，listB = [ 5，6，1，8，4，5 ]，skipA = 2，skipB = 3

输出：IntersectVal at ‘8’

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例1：

输入：intersectVal = 0, listA = [ 2，6，4 ]，listB = [ 1，5 ]，skipA = 3，skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

（2）题目解析及思路

我们要判断是否为相交链表，并找出相交点，而且不能破坏原链表的结构。我们先要清楚相交链表的概念，题目给的图示就很直观，有两个链表的最后一个节点不指向空指针，但是同时指向一个结点。还要注意的是，不能形成环形链表，就是一个链表出现头尾相连的情况。

这道题我会提供两个思路。

思路一：

我们观察相交链表，会发现不管从A链表出发，还是B链表出发，在指向空指针之前的结点是相同的，我们可以根据这个判断是否为相交链表。并在遍历AB链表的时候，记录链表从A出发和从B出发的长度，算出差距多少步。定义两个指针变量，让长的链表指针变量先走差距步，然后两个链表指针同时走，当走的过程中，两个指针相同时，必然是相交的节点。

代码如下：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1;
    while(tailA->next)
    {
        lenA++;
        tailA = tailA->next;
    }
    int lenB = 1;
    while (tailB->next)
    {
        lenB++;
        tailB = tailB->next;
    }
 
    if(tailA != tailB)
    {
        return NULL;
    }
    //abs时绝对值
    int gap = abs(lenA - lenB);
    //先假设A链表是长链表，再比较，如果不是再重新赋值
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if (lenA < lenB)
    {
        shortlist = headA;
        longlist =headB;
    }
    // 长的先走差距步，再同时走交点
    while(gap--)
    {
        longlist = longlist->next;
    }
 
    while(longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
 
    return longlist;
}

思路二：

思路二更加巧妙，我用图示展示更直观。A链表结点总个数用totalA表示，在相交结点之前A链表节点个数用lenA表示，相交结点之后公共部分用comlenth表示。B链表同理。

totalA = lenA + comlenth

totalB = lenB + comlenth

• 当curA和curB这两个指针同时走到最后一个结点时，curA走了totalA步，curB走了totalB步

• 当遇上空指针的时候，把curA指针指向链表B，把curB指针指向链表A。继续走。

• 当都走到相交结点时，我们会发现curB走的步数是totalB + lenA，是八步，curA走的步数是totalA + lenB，也是八步。这难道是巧合吗？还记得最开始的式子吗，我们做个化简，会发现按照我刚刚的方式走到相交结点时，他们俩的步数一定是一样。

totalA = lenA + comlenth                                                                                                        

totalB = lenB + comlenth

将其带入到curAlen和curBlen中，

curAlen = totalA + lenB = (lenA + comlenth) + lenB = (len A + lenB) + comlenth

curBlen = totalB + lenA = (lenB + comlenth) + lenA = (len A + lenB) + comlenth

• 如果不是相交链表呢？还是想按照上面的办法，当走到各自链表最后一节点，遇到空指针，从头开始，但是位置互换，放走到空指针时，步数刚好相同都是两个链表个数之和返回空指针。

那么代码怎么写呢，先要注意如果有其中一个链表为空，就无法形成相交链表，直接返回空。先创建两个指针curA和curB，写一个while循环，结束条件是curA = curB的时候，最后返回其中一个指针变量即可。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    if (headA == NULL || headB == NULL) 
    {
        return NULL;
    }
 
 
    struct ListNode *curA = headA, 
    struct ListNode *curB = headB;
    while (curA != curB) 
    {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }
    return curA;
}
 

---

总结

这次七道链表OJ题目的解析可以说是干货满满，建议收藏。每做一道题，可以参考上面的图示来分析理解思路，多画图有助于你思路顺畅，后期写代码不卡壳。事后可以尝试自己总结其中用到的方法，话不多说，练起来！

创作不易，希望这篇文章能给你带来启发和帮助，如果喜欢这篇文章，请留下你的三连哦，你的支持的我最大的动力！！！