目录
? 解题思路:????????图片解析:????????代码示例:
? ? 解题思路:????????方法一:????????方法二 :? ? ? 方法对比:????????代码示例:
? ? 解题思路:????????证明过程:????????代码示例:
? ? 解题思路:?????? ?画图分析:????????代码示例:
回文链表:牛客_链表的回文结构
? 解题思路:
? ? ? ? 1.先用快慢指针找到中下节点力扣876_链表中间节点
? ? ? ? 2.反转后面部分节点力扣206_反转单链表
? ? ? ? 3.进行判断
? ? ? ?图片解析:
代码示例:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
//找到中间节点
if(A==NULL || A->next==NULL){
return true;
}
ListNode *slow =A;
ListNode *fast =A;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}//slow 为中下节点
//反转后面的链表
ListNode* per=NULL;
ListNode* cur=slow;
ListNode* next=slow->next;
while(cur){
cur->next=per;
per=cur;
cur=next;
if(next) next=next->next;
}//per为尾巴节点
ListNode* head=A;
while(per && head){
if(per->val==head->val){
per=per->next;
head=head->next;
}
else{
return false;
}
}
return true;
}
};相交链表:力扣160_相交链表
? ? 解题思路:
方法一:
? ? ? ? 1.遍历A,B 求出链表长度A,B (假设B比A长)
????????2.B先走 (B-A) 步,使A,B同起点
? ? ? ? 3.A,B同时出则返回NULL,如果相遇,则相遇点为相交节点
? ? ? ?
方法二 :? ? ? ?????????
????????假设A B链表相交,c为相交部分,则有? ?a+c+b=b+c+a.
????????所于,我们可以将A B链表进行链接,
????????当链表A 走完a+c后 令他走向 B链表
????????当链表B走完b+c后 令他走向 A链表
????????则当A走完 a+c+b??B走完b+c+a 时他们就相遇了,返回相遇节点? ? ? ?
????????如果不相交,则走A走完A+B,B走完B+A 返回NULL
?方法对比:
? ? ? ? 方法一相对于方法二,优点在于更易于理解.并且在大多数情况下时间复制度是相同的.
? ? ? ? 而方法二的优势就在于,当链表A和B一样长的时候,他并不需要先遍历完链表长度,就可以直接得到答案.?且实现代码也更为简洁.(稍后你就会看见方法二简洁的代码,而方法一由于代码实现并非这么难,这里就不做演示)
代码示例:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//A+C+B == B+C+A //c表示链表的交叉部分
struct ListNode* A=headA;
struct ListNode* B=headB;
while(headA!=headB){
headA=(headA?headA->next:B);
headB=(headB?headB->next:A);
// if(headA){
// headA=headA->next;
// }
// else{
// headA=headB;
// }
// if(headB){
// headB=headB->next;
// }
// else{
// headB=headA;
// }
}
return headA;
}环状链表:力扣142_环状链表入口点
? ? 解题思路:
? ? ? ?1.快慢指针 fast走2步 slow走1步,如果链表有环,则必然相遇.(就像操场跑步,跑的快的必然追上跑的慢的)
????????????????????????????????????????为什么fast是走2步,而不能是走3步或4步
? ? ?? 2.如果有环,一个指针从相遇点出发,另一个指针从入口点出发,每次走一步,则必然在入口点相遇
? ? ? ?证明过程:
???代码示例:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
if(head==NULL||head->next==NULL)return NULL;//无环
struct ListNode* slow=head;
struct ListNode* fast=head;
//寻找相遇点
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(slow==fast){//找到相遇点
while(slow!=head){ 寻找入口点
slow=slow->next;
head=head->next;
}
return slow; //返回入口点
}
}
return NULL; //无环
}随机链表:力扣138_随机链表深拷贝
? ? 解题思路:
? ? ? ? ? 1.拷贝节点在原来的节点后面.
? ? ? ? ? 2.拷贝random节点. p->next->random=p->random->next
? ? ? ? ? 3.拆分链表? ? ??
? ? ? ? 画图分析:
?代码示例:
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
struct Node* copyRandomList(struct Node* head) {
if(head==NULL)return head;
struct Node* cur=head;
//复制节点 7->7->13->13->11->11 '''->1->1->null
while(cur){
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
if(copy==NULL){return NULL;}
copy->next=cur->next;
copy->val=cur->val;
cur->next=copy;
cur=copy->next;
}
//复制random
cur=head;
struct Node* copy=cur->next;
while(cur){
copy=cur->next;
copy->random=(cur->random==NULL?NULL:cur->random->next);
cur=cur->next->next;
}
//拆分链表
cur=head;
struct Node* p=cur->next;
while(cur){
copy=cur->next;
cur->next=copy->next;
cur=cur->next;
copy->next=(cur==NULL?NULL:cur->next);
}
return p;
}