链表算法题（OJ刷题超详细讲解）

1.返回倒数第K个节点，

OJ链接：返回倒数第K个节点

本题有很多种解法，例如创建数组，或者将原链表反转等等，这里们使用快慢指针，只需要遍历一遍链表，并且空间复杂度为O(1)，时间复杂度为O(N)

我们先来画图分析一下

我们让快指针fast先走k步，然后再一起走，最后返回slow的值。

代码如下：

typedef struct ListNode ListNode;

int kthToLast(struct ListNode* head, int k){
    assert(head);
    ListNode*slow = head;
    ListNode*fast = head;
    while(k--)
    {
         fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow->val;

}

2.链表的回文结构

OJ链接：链表的回文结构

本题要求时间复杂度为O(n),额外空间复杂度为O(1)，该怎么写呢？

分析：

我们要想证明它是个回文结构，首先我们要先知道回文结构是什么，从前往后和从后往前是完全相同的，以中间节点为中心这个链表是对称的，举个例子比如12321和1221这两个都是回文，如果是123123这个还是回文吗?这种就不是回文了，如果需要证明这个链表是回文，那么我们是不是就可以先找到中间节点，然后再反转一下中间节点及之后的节点，如上图我们找到中间节点2之后把中间节点及之后的节点都反转了，然后让中间节点与首节点进行判断值是否相等，万一是奇数个节点呢，奇数个也没事我们左边的2并没有改变它的next所以2指向的还是3，3和3自己比，最后3指向的就是NULL了。

代码如下：

//找中间节点
struct ListNode* middleNode(ListNode* head)
{
    struct ListNode* slow = head,*fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//反转
struct ListNode *reverseList(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;
}

    bool chkPalindrome(ListNode* A) {
        // write code here

        struct ListNode*mid = middleNode(A);
        struct ListNode*rmid = reverseList(mid);
        while(rmid && A)
        {

       
            if(A->val != rmid->val)
                return false;
            
            A = A->next;
            rmid = rmid->next;
        
        }
    return true;
}
};

3.相交链表

OJ链接：相交链表

判断链表是否相交，如果说我们一个一个比较的话，A链表的节点依次跟B链表所有节点比较，A某个节点跟B某个节点相等，这个节点就是交点，这样太麻烦了，而且时间复杂度为O(N^2)，那么我们可以先遍历链表，判断两个链表的尾节点是否相等，如果相等那么就一定相交，在我们遍历链表的时候，我们可以顺便计算出链表的相对值，然后让长的链表先走差值的距离，在同时走，只要两个节点相等就是相交

画图演示：

代码如下：

 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode*curA = headA,*curB = headB;
    int lenA = 1,lenB = 1;
    while(curA->next)
    {
        curA = curA->next;
        ++lenA;
    }
    while(curB->next)
    {
        curB = curB->next;
        ++lenB;
    }
    //尾节点不相等就是不相交
    if(curA->next != curB->next)
    {
        return NULL;
    }
    //长的先走差距步，在同时走，第一个相等就是相交
    //假设法
    int gap = abs(lenA-lenB);//求绝对值
    ListNode* longList = headA,*shortList = headB;
    if(lenB > lenA)
    {
        longList = headB;
        shortList = headA;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return shortList;
}

如上代码中我们用到了假设法，如果我们假设错了，就修正一下，A长还是B我们不关注，我们只要知道longList是长的shortList是短的就行，假设法可以使得我们逻辑变得更加简单。

注：我们一定要用地址进行判断，如果用值判断可能会有重复的值

4.随机链表的复制

OJ链接：随机链表的复制

深拷贝就是拷贝一个值和指针指向跟当前链表一模一样的链表

这道链表题每个节点里多了个指针指向随机节点，也有可能指向空，然后深拷贝一份，如果我们直接遍历然后拷贝呢？硬拷贝是可以的，但是有个问题，随机指针（random）指向的值如何在新链表中实现呢，如果我们去链表中查找，那么万一有重复的值怎么办呢，这就会导致没拷贝成功，如果真要用这种暴力查找，就要算相对位置，而且它的时间复杂度为O(N^2)。

我们可以先拷贝链表，然后把拷贝的链表插入到原节点的后面，每个拷贝节点和原节点建立了一个关联关系

然后我们在控制random，如下图所示，我们7的random指向的为空，那么我们拷贝节点7的random也要指向空，我们拷贝节点7就在原节点的后面，所以处理起来很方便，那么13的random指向的是7我们如何拷贝呢，拷贝节点的random指向的就是cur->random->next，最后再将拷贝节点拿下来尾插，成为一个新的链表，虽然我们破坏了原链表的结构，我们可以选择恢复原链表也可以不恢复，题目没有要求。

代码如下：

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
    Node* cur = head;
    // 拷贝节点插入在原节点后面
    while(cur)
    {
        Node* copy = (Node*)malloc(sizeof(Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
    //控制random
    cur = head;
    while(cur)
    {
        Node*copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        cur = copy->next;
    }
    //拷贝节点取下来尾插成为新链表，然后恢复原链表（不恢复也可以）
    Node *copyhead = NULL,*copytail = NULL;
    cur = head;
    while(cur)
    {
        Node*copy = cur->next;
        Node*next = copy->next;
        if(copytail == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }
        //恢复原链表
        cur->next = next;
        cur = next;
    }
    return copyhead;
}

5.环形链表

OJ链接：环形链表

思路：快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。

画图演示：

代码如下：

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

}

在面试中面试官可能会问的两个问题，如下

1.为什么一定会相遇，没有可能会错过，永远追不上？请证明

证明：假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇

2.slow一次走一步，fast走3步4步5步n步能追上吗？请证明

证明如下：

这里我们假设fast一次走3步，当slow进环时，fast开始追击slow，过程中距离变化如下：

偶数奇数

N N

N-2 N-2

N-4 N-4

.... ....

4 3

2 1

1 -1

0

每追击一次，距离缩小2

0就是追上了

追成-1就是刚好错过，开始新一轮的追击了

距离变成C-1,(假设C是环的长度)

总结一下：

1、N是偶数，第一轮就追上了

2、N是奇数，第一轮追击会错过，距离变成C-1

a、如果C-1是偶数，下一轮就追上了

b、如果C-1是奇数，那么就永远追不上

我们在来分析一下会不会出现永远追不上的可能，上面的b条件成不成立呢？

永远追不上是有条件的，同时存在N是奇数且C是偶数，那么就永远追不上

那么有没有可能这两个条件不存在？证明一下

证明如下：

假设slow进环时，fast跟slow距离是N

slow走的距离是L

fast走的距离：L+x*C+C-N

slow进环时，假设fast已经在环里转了x圈

fast走的距离是slow的3倍

3*L= L+x*C+C-N

化简一下变成：2*L = (x+1)*C-N

偶数 = （x+1）*偶数-奇数

N是奇数时，C也是奇数

N是偶数时，C也是偶数

只有奇数-奇数才能变成偶数

（x+1）*偶数一定是偶数

所以N是奇数且C的偶数不能同时存在，永远追不上的条件不成立

结论：

N是偶数，第一轮就追上了

N是奇数，第一轮追不上，C-1是偶数第二轮就追上

6.环形链表II

OJ链接：环形链表II

我们依旧可以使用快慢指针，slow走一步fast走两步，当它们在环里相遇时，让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

在我们面试的时候面试官可能会问这样的问题，为什么它们最终肯定会在入口点的位置相遇呢？请证明一下？

证明如下：

假设入环前的这段距离是L

假设相遇点到入环点的距离是N

长的环度是C

假设x是fast在环里转了x圈（x>=1）

相遇时：

slow走的路程：L+N

fast走的路程：L+x*C+N

fast走的路程是slow2倍

2*(L+N)=L+x*C+N

L+N = x*C

L=x*C-N

最终化简成这样：L=(x-1)*C+C-N

假如x=1，那么L=C-N，正好是相遇点到进环点的距离与入环之前的距离相等，让一个节点从头开始遍历，一个从相遇点开始，最终在入环的第一个节点相遇，证明了我们肯定会在入口点的位置相遇，如果x不唯1呢，那也会相遇，无非就是在环里多走了几圈，最后还是会在入环的第一个节点相遇

代码如下：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fase = head;
    
    while(fase && fase->next)
    {
        slow = slow->next;
        fase = fase->next->next;
        //相遇
        if(slow == fase)
        {
            struct ListNode*meet = slow;
            while(meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}