🌕写在前面

---

• 🍊博客主页F1a;kikoking的江湖背景
• 🎉欢迎关注🔎点赞👍收藏⭐️留言📝
• 🌟本文由 kikokingzz 原创，CSDN首发！
• 📆首发时间：🌹2021年12月02日🌹
• 🆕最新更新时间：🎄2021年12月02日🎄
• ✉️坚持和努力一定能换来诗与远方！
• 🙏作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢感谢感谢！
• 前文简介：
• 第一话·彻底搞清数据结构中的·逻辑结构&存储结构
• 第二话·彻底搞懂数据结构之·算法复杂度
• 第三话·408必看顺序表之·人生不是“顺序表”
• 第四话·数据结构必看之·单链表就这？
• c语言·链表基础必刷21题 —— 三板斧（上）

---

---

目录

  🌕写在前面

📄题7.链表的回文结构

✅思路一：指针从两端向中间走

✅思路二：开一个数组 

✅思路三：找中间结点+后逆置

📄题8.相交链表

✅思路一

✅思路二

📄题9.环形链表

✅思路一：使用快慢指针

📄关于本题-->面试延伸的问题

📄题10.环形链表II

✅思路一：推公式

✅思路二：相交链表的变式表示

📄题11.复制带随机指针的链表

✅思路一：拷贝结点链接在后边

📄题12.对链表进行插入排序

✅思路一

📄题13.删除链表中重复的结点

✅思路一：多指针问题

---

📄题7.链表的回文结构

OR36 链表的回文结构https://www.nowcoder.COM/PRactice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activITy/oj&qru=/ta/2016test/question-ranking

https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

@H_777_101@

✅思路一：指针从两端向中间走

两侧指针指向元素相同-->向中间走

但由于是单链表，尾指针没法倒着走！数组可以这么做！失败！

---

✅思路二：开一个数组 

开一个int a[900],链表的数据放到数组，用数组判断-------------------->空间复杂度O(N)

---

✅思路三：找中间结点+后逆置

1.先找到中间结点---->快慢指针

2.后半部分逆置--->

 3.与后半段比较

     //找中间结点，快慢指针
    struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *fast = head, *slow = head;
    while(fast&&fast->next)
    {
        slow=slow->next;//slow走一步
        fast=fast->next->next;//fast走两步
    }
    return slow;
   }

 //使用头插法将链表逆置                       
    struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur=head , *newHead=NULL;
    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next=newHead;
        newHead=cur;
        cur=next;
    }
    return newHead;
    }

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

  
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid=;middleNode(A);//找中间结点
        struct ListNode* rhead=reverseList(mid);//将中间结点的后续元素逆置
        while(A&&rhead)//前后两组元素比较，其中一组结束即结束
        {
            if(A->val!=rhead->val)
                return false;
            else
            {
                A=A->next;
                rhead=rhead->next;
            }
        }
        return  true;
    }
};

成功运行了，但是不知道各位有没有仔细去发现一件事，根据“比较”程序的代码，我们可以发现对于偶数个数字的比较是很容易理解的，rehead最后会为空，跳出程序，但是对于奇数个数字，为什么可以跑过呢？

---

📄题8.相交链表

160. 相交链表https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/

 对于本题，相交只可能是下图情况，可见题目给的也是这种情况！

✅思路一

Q：判断两个链表是否相交

·找两个链表中的结点地址有无相同点

该方法@R_206_1304@有点高，不太推荐这种方法 

---

✅思路二

Q：判断两个链表是否相交

step1.比较尾指针

---

step2.若相交，求交点

1.计算出两个链表的长度，让长的链表先走差距步

2.再同时走，第一个相同的结点就是交点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    if(headA==NULL||headB==NULL)//如果有空链表，必然不相交
    {
        return NULL;
    }
    struct ListNode* curA=headA, *curB=headB;
    int lenA=0,lenB=0;
    while(curA->next)//一直遍历到最后一个结点
    {
        curA=curA->next;//curA有可能是空指针,在上述添加判断
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    //不相交-
    if(curA!=curB)
    return NULL;

    //长的先走差距步，再同时走
    struct ListNode* longlist=headA, *shortlist=headB;//假设A长B短
    if(lenB>lenA)//如果B长A短
    {
        longlist=headB;
        shortlist=headA;
    }
    int gap = abs(lenB-lenA);//abs取绝对值
    while(gap--)//gap--走gap步
    {
        longlist=longlist->next;
    }
    printf("1");
    while(longlist!=shortlist)
    {
        shortlist=shortlist->next;
        longlist=longlist->next;
    }
    return shortlist;
}

---

📄题9.环形链表

141. 环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

✅思路一：使用快慢指针

1.快指针fast-->一次走两步

2.慢指针slow-->一次走一步

3.如果带环，slow和fast会在环里相遇

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head, *fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;//fast走两步
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

---

📄关于本题-->面试延伸的问题

1.为什么slow走一步，fast走两步，他们一定会在环里面相遇，会不会永远追不上？

证明：slow进环的时候，fast一定已经在环内。假设slow进环的时候，fast和slow的距离是N（fast追slow，追N步），slow每走一步，fast往前走两步，距离缩小一步；也就是说slow走N步，fast和slow间距离缩小N，最后就相遇了。

2.slow走一步，fast走3步行不行？为什么？

证明：slow每走1步，fast走3步时，距离每次缩小2，对于距离N，只有N为偶数时，那么一定会相遇，但如果N是奇数，那么会错过。假定环的长度为C，错过后，此时fast和slow的差距变为（C-1）,如果C-1为奇数，那么slow和fast永远不会相遇，因为slow和fast之间的距离缩减一直是一个偶数（2）

---

📄题10.环形链表II

142. 环形链表 II

https://leetcode-cn.com/problems/linked-list-cycle-ii/

✅思路一：推公式

Q1：为什么slow走了L+X呢？slow不能多走一圈才相遇吗？

A1：因为slow进环以后在一圈内fast就会追上slow，所以slow走的是L+X，如果slow都走了一圈了，那么fast已经走了两圈了，早就追上了！

由于快指针fast是慢指针slow移动距离的2倍，因此可以得到
公式如下：
2(L+X)=L+X+n*C
   L+X=n*C
     L=n*C-x
-------------------->

由上述公式可以得出：当一个指针从相遇点走，一个指针从起点走时，它们会在入口点相遇

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            //相遇
            struct ListNode* meet=fast;
            //通过推论证明：一个指针从head走，一个指针从meet走
            //他们会在入口点相遇
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

---

✅思路二：相交链表的变式表示

---

📄题11.复制带随机指针的链表

138. 复制带随机指针的链表

https://leetcode-cn.com/problems/copy-list-with-random-pointer/

我们可以方便的复制出每一个结点对应的next，但是随机指针指向的元素是本题的难点

难点：拷贝结点的random——处理效率太低，太复杂

1.例如上述示例1中，第二个结点的random指向7，新链表并不知道7的地址，需要遍历查找，时间复杂度是O(N)，因此处理每个结点的random的时间复杂度就是O(N*N)

2.如果这个链表里有很多7，random指向的7就不知道是哪个7，还需要确定是第几个值为7的结点

✅思路一：拷贝结点链接在后边

 

struct Node* copyRandoMList(struct Node* head) {
	//step1 拷贝结点在原结点的后面，建立对应关系
    struct Node* cur=head;
    while(cur)
    {
        struct Noed* next=cur->next;
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy-val=cur-val;
        cur->next=copy
        copy->next=next;
        
        cur=next;
    }

  //step2.处理copy结点的random
    cur=head;
    while(cur)
    {
        struct Node*copy=cur->next;
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next; //这句是精华
        }
        cur=copy->next;
    }

🍓算法巧妙之处：

1.通过将拷贝结点链接在原结点后边------->使得拷贝的random的结点在原结点的后边；

2.如此只要找到random指向的原结点，也就找到了拷贝结点的位置，避免了在新链表中去查找

@H_512_532@

    //steP3.把拷贝结点取下来链接到一起，恢复原链表
    cur=head;
    struct Node* copyHead, *copyTail;
    copyHead=copyTail=(struct Node*)malloc(sizeof(struct Node));
    //取哨兵位，方便尾插
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        //尾插
        copyTail->next=copy;
        copyTail=copyTail->next;
        cur->next=next;
        cur=next;
    } 
    struct Node*Guard=copyHead;
    copyHead=copyHead->next;
    free(guard);
    guard=NULL;
    return copyHead;

---

📄题12.对链表进行插入排序

147. 对链表进行插入排序

https://leetcode-cn.com/problems/insertion-sort-list/

 

 ✅思路一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* insertionSortList(struct ListNode* head){
    if(head==NULL||head->next==NULL)
        return head;

    struct ListNode* sortHead = head;
    struct ListNode* cur = head->next;
    sortHead->next=NULL;

    while(cur)//2.终止条件
    {
        //3.迭代条件
        struct ListNode*next=cur->next;
        
        //将cur结点插到前面有序区间
        struct ListNode* p=NULL, *c=sortHead;
        while(c)
        {
            if(cur->val<c->val)
            {
                break;
            } 
            else
            {
                p=c;
                c=c->next;
            }
        }
        if(p==NULL)
        {
            cur->next=c;
            sortHead=cur;
        }
        else
        {
            p->next=cur;
            cur->next=c;
        }
        cur = next;
    } 
    return sortHead;
}

---

📄题13.删除链表中重复的结点

JZ76 删除链表中重复的结点https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&&tqId=11209&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&&tqId=11209&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

✅思路一：多指针问题

删除问题-->删除重复的-->双指针问题 

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplication(struct ListNode* pHead ) {
    if(pHead==NULL||pHead->next==NULL)
    return pHead;
    
    struct ListNode* prev=NULL,*cur=pHead,*next=pHead->next;
    while(next)
    {
        if(cur->val==next->val)
        {
            //删除重复
            while(next && cur->val==next->val)//要防止空指针，使用操作符的短路效果
            {
                next=next->next;
            }
            //删掉cur到next前的结点
            while(cur!=next)
            {
                struct ListNode* del=cur;
                cur=cur->next;
                free(del);
            }
            if(prev==NULL)
            {
                pHead=cur;
            }
            else
            {
                prev->next=cur;
            }
           if(next)
           {
           next=next->next;
           }
        }
        else
       {
            //同时往后挪动
            prev=cur;
            cur=next;
            next=next->next;
        }
    }
    return pHead;
}