💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
📆 个人专栏： 🔹数据结构与算法🔹C语言进阶
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
- 链表的回文结构
- 160.相交链表
- 141.环形链表（LeetCode）
- leetcode142.环形链||
- LeetCode138.复制带随机指针的链表
前言：
| 最近在刷题的铁子们，你们在做题的时候一定要画图，人的思维固然很强，但是把图画好是真香啊！遇到BUGl了照着图分析，十分简洁明朗，事半功倍。 |
链表的回文结构
题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
测试样例： 1->2->2->1 返回：true
思路：
1.找到中间节点
2.从中间节点往后逆置
3.定义快慢指针，向后遍历判断是否相等。
class PalindromeList {
public:
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head,*fast = head;
while(fast&& fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reveseList(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;
}
bool chkPalindrome(ListNode* head) {
// write code here
struct ListNode* mid = middleNode(head);
struct ListNode* rmid = reveseList(mid);
while(rmid && head)
{
if(rmid->val !=head->val)
{
return false;
}
rmid = rmid->next;
head = head->next;
}
return true;
}
};
160.相交链表
题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB
中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB
传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
思路：
1.分别计算listA,listB链表的长度
2.取两绝对值，对齐两个链表，同时开始遍历，当相同就相交了。
代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA = headA,*curB = headB;
//分别计算A，B链表的长度
int lenA =1,lenB =1;
while(curA->next)
{
curA = curA->next;
lenA++;
}
while(curB->next)
{
curB = curB->next;
lenB++;
}
//此时curA，B都已指向最后节点，如果不相等，则说明不相交
if(curA != curB)
{
return NULL;
}
//求出相差的步数
int n = abs(lenA-lenB);
struct ListNode* LongList = headA,* ShortList = headB;
if(lenA<lenB)
{
LongList = headB;
ShortList = headA;
}
//先让长的链表走n步，与短链表对齐
while(n--)
{
LongList = LongList->next;
}
//同时走，找相同；
while(LongList!=ShortList)
{
LongList = LongList->next;
ShortList = ShortList->next;
}
return ShortList;
}
141.环形链表（LeetCode）
给你一个链表的头节点 ，判断链表中是否有环。head
如果链表中有某个节点，可以通过连续跟踪 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。nextpos
如果链表中存在环 ，则返回 。否则，返回 。truefalse
思路：
代码：
bool hasCycle(struct ListNode *head) {
struct ListNode *fast = head,*low = head;
while(fast && fast->next)
{
fast = fast->next->next;
low = low->next;
if(fast == low)
{
return true;
}
}
return false;
}
leetcode142.环形链||
题目要求：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
思路分析：
🔸如果链表存在环，则fast和slow会在环内相遇，定义相遇点到入口点的距离为X,定义环的长度为C,定义头到入口的距离为L,fast在slow进入环之后一圈内追上slow,则会得知：
🔸slow所走的步数为:L + X
🔸fast所走的步数为：L + X + N * C
并且fast所走的步数为slow的两倍，故：
🔸2*(L + X) = L + X + N * C
即： L = N * C - X
所以从相遇点开始slow继续走，让一个指针从头开始走，相遇点即为入口节点
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode* fast,*slow;
slow = fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
struct ListNode* meet = slow;
while(head != meet)
{
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}
LeetCode138.复制带随机指针的链表
题目要求：
·读题·：首先，这道题目的意思是完整的复制一遍链表，难点在于每个节点有一个随机指针，由于题目要求不能指向原来链表，所以他的复制成了一个难点。
解决步骤：
1.在原链表每个节点之后插入一个复制节点 （复制前一个节点）。
2.给复制节点中的random进行指向。
3.把所有的复制节点拿下来整理成新列表，
思路图：
代码：
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
//复制每个节点并插入到相应节点之后
while(cur)
{
struct Node* next = cur->next;
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//给copy赋值内容
copy->val = cur->val;
//插入
cur->next = copy;
copy->next = next;
//向后移动过cur指针和next指针
cur = next;
}
//处理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;
}
//将新链表整理出来
cur = head;
//制造一个哨兵位作为新链表的头结点，便于插入
struct Node* copyhead = (struct Node*)malloc(sizeof(struct Node));
copyhead->val = 1;
copyhead->next = NULL;
copyhead->random = NULL;
//定义一个节点，遍历新链表。为了保存原链表的头。
struct Node* pcopyhead = copyhead;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
//尾插到新链表
pcopyhead->next = copy;
pcopyhead = pcopyhead->next;
//恢复原链表
cur->next = next;
cur = next;
}
return copyhead->next;
}
注意点：切记如果使用了哨兵位那么一定要给它进行初始化。
