[ 1500元做网站_验收满意再付款! ]_沛县网络公司,东莞桥头网站设计,网站升级对外解决方案,企业网站建设都需要什么准备文章目录 一、返回倒数第k 个节点二、链表的回文结构三、相交链表 一、返回倒数第k 个节点
原题链接#xff1a;返回倒数第k 个节点 利用快慢指针的方法#xff1a;先让fast走k步#xff0c;然后fast和slow一起走#xff0c;直到fast为空#xff0c;最后slow指向的结点就… 文章目录 一、返回倒数第k 个节点二、链表的回文结构三、相交链表 一、返回倒数第k 个节点
原题链接返回倒数第k 个节点 利用快慢指针的方法先让fast走k步然后fast和slow一起走直到fast为空最后slow指向的结点就是目标结点
int kthToLast(struct ListNode* head, int k)
{struct ListNode* slow head;struct ListNode* fast head;while(k--){fast fast-next;}while(fast){fast fast-next;slow slow-next;}return slow-val;
}
二、链表的回文结构
原题链接链表的回文结构 对于这道题可以分为三个步骤 首先找到链表的中间结点mid 其次从中间结点开始将链表逆置 最后将指向原链表的指针A与指向逆置后的指针rmid的结点数据进行比较遍历链表 class PalindromeList
{
public://找到中间结点struct ListNode* FindMid(struct ListNode* head){struct ListNode* slow head;struct ListNode* fast head;while(fast fast-next){fast fast-next-next;slow slow-next;}return slow;}//逆置链表struct ListNode* Reserve(struct ListNode* head){struct ListNode* n1 NULL;struct ListNode* n2 head;struct ListNode* n3 n2-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3){n3 n3-next;}}return n1;}bool chkPalindrome(ListNode* A){struct ListNode* mid FindMid(A);struct ListNode* rmid Reserve(mid);while(A rmid){if(A-val ! rmid-val){return false;}A A-next;rmid rmid-next;}return true;}
};三、相交链表
原题链接相交链表 关于链表的相交不是交叉形状而是Y字形 那么如何解决这个问题呢 可以创建两个指针变量分别指向各自的头结点然后遍历找到尾结点并且比较尾结点是否相同相同就表示两个链表一定相交不相同直接返回NULL 确定两个链表相交那么如何找到相交的头结点呢 鉴于两个链表的长度不一定相等应该在上述遍历链表的时候记录下各自链表的长度然后让指向长度大的链表的指针先走差距步这样两个指针距离相交结点的距离就相等了直接循环遍历找到目标结点即可 那么哪个链表更长呢 这里可以用假设法假设长的为A后面再判断是否A与B的大小这样可以省了不少代码量更加方便
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* pcurA headA;int lenA 1;struct ListNode* pcurB headB;int lenB 1;while(pcurA-next){pcurA pcurA-next;lenA;}while(pcurB-next){pcurB pcurB-next;lenB;}//判断尾结点是否相等if(pcurA ! pcurB){return NULL;}//假设法//假设longnode headA shortnode headBint gap abs(lenA - lenB);struct ListNode* longnode headA;struct ListNode* shortnode headB;if(lenA lenB){longnode headB;shortnode headA;}//走差距步while(gap--){longnode longnode-next;}while(longnode ! shortnode){longnode longnode-next;shortnode shortnode-next;}return longnode;
}
