需要的请点下面：
-> 给大家推荐一款很火爆的刷题、面试求职网站 <-
文章题目来源力扣或牛客
🎈 力扣（LeetCode）全球极客挚爱的技术成长平台
LeetCode官网： https://leetcode-cn.com/problem-list/e8X3pBZi/
牛客网-笔试题库：[ https://www.nowcoder.com
]( https://www.nowcoder.com)
7.回文链表
来源：牛客网
链接： OJ链接
- ✨思路
先找到中间节点，把后半部分逆置，然后再依次比较是否相等
struct ListNode* reverseList(struct ListNode* head){
struct ListNode*n1=NULL,*n2=head;
while(n2)
{
struct ListNode*n3=n2->next;
n2->next=n1;
n1=n2;
n2=n3;
}
return n1;
}
struct ListNode* middleNode(struct ListNode* head){
struct ListNode*slow=head,*fast=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* mid=middleNode(A);//找中间节点
struct ListNode*cur2=reverseList(mid);//从中间节点开始逆置
struct ListNode*cur1=A;
while(cur2)//依次比较
{
if(cur1->val!=cur2->val)
return false;
cur2=cur2->next;
cur1=cur1->next;
}
return true;
}
8.相交链表
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/intersection-of-two-linked-lists
- ✨思路
仔细观察可以发现，如果链表相交的话，那么它们都有一个共同的特点，那就是尾节点相同，所以可以利用这个特点来解决链表是否相交
至于返回相交点，我们可以依次算出每一个链表的长度，然后让长的那个一个先走差距步，然后再同时走，直到相等即为相交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* cur1=headA,*cur2=headB;
int count1=1,count2=1;
//找尾
while(cur1->next)
{
cur1=cur1->next;
count1++;
}
while(cur2->next)
{
cur2=cur2->next;
count2++;
}
//尾节点不相等则不相交
if(cur1!=cur2)
return NULL;
struct ListNode*longList=headA,*shotList=headB;
if(count1 < count2 )
{
longList=headB;
shotList=headA;
}
int k=abs(count1-count2);
//让长的先走差距步
while(k--)
{
longList=longList->next;
}
//相等地方即为入口
while(longList!=shotList)
{
longList=longList->next;
shotList=shotList->next;
}
return longList;
}
9.环形链表丨
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/linked-list-cycle
- ✨思路
快慢指针法：定义两个指针fast和slow，fast一次走两步，slow一次走一步，最后如果相等则说明存在环，如果fast遇到NULL，则说明没有环
证明：
bool hasCycle(struct ListNode *head) {
struct ListNode*fast,*slow;
fast=slow=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
return true;
}
return false;
}
10.环形链表 II
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/linked-list-cycle-ii
- ✨思路一
快慢指针法：定义两个指针fast和slow，fast一次走两步，slow一次走一步，相等位置为相遇点，在相遇点断开，转化成两个链表相交求交点问题
- ✨思路二
这个解法很妙，就是从找到相遇点后，一个指针从相遇点开始，另一个指针从头开始，同时遍历，直到相等就是入环点，这个可以用数学公式证明
//思路二的代码实现
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*fast,*slow;
fast=slow=head;
while(fast && fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)//有环
{
struct ListNode*cur=head;
while(cur!=slow)//入口点
{
cur=cur->next;
slow=slow->next;
}
return cur;
}
}
return NULL;
}
11.复制带随机指针的链表
来源：力扣（LeetCode）
链接： https://leetcode.cn/problems/copy-list-with-random-pointer
- ✨思路
这题主要的难点在于随机指针random的复制，搞定了这个随机指针，那么问题就迎刃而解了
首先，我们可以把每一个复制节点的尾插到每一个原节点的后面，然后依次根据原节点的random把复制节点的random连接上，最后再恢复原链表，取复制链表
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head,*next=head,*copy=NULL;
//复制节点尾插到原节点中
while(cur)
{
next=cur->next;
copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
cur->next=copy;
copy->next=next;
//迭代
cur=next;
}
//复制randam
cur=head;
while(cur)
{
copy=cur->next;
next=cur->next->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
//迭代
cur=next;
}
//恢复原链表
struct Node*copyhead=NULL,*tail=NULL;
cur=head;
while(cur)
{
copy=cur->next;
next=cur->next->next;
if(copyhead==NULL)
{
copyhead=tail=copy;
}
else
{
tail->next=copy;
tail=tail->next;
}
cur->next=next;
//迭代
cur=next;
}
return copyhead;
}
