网站建设 管理与维护试题,入门网站分析应该怎么做,昆明酒店网站建设,宝安住房和建设局网站一、返回链表倒数第k个节点
. - 力扣#xff08;LeetCode#xff09; 本体思路参展寻找中间节点的方法#xff0c;寻找中间节点是定义快慢指针#xff0c;快指针每次走两步#xff0c;慢指针每次走一步#xff0c;当快指针为空或者快指针的下一个节点是空时#xff0c;…一、返回链表倒数第k个节点
. - 力扣LeetCode 本体思路参展寻找中间节点的方法寻找中间节点是定义快慢指针快指针每次走两步慢指针每次走一步当快指针为空或者快指针的下一个节点是空时此时的慢指针指向的节点就是中间节点并且此时的快指针和慢指针之间的节点个数就是整个链表的一半
据此同理可以定义快慢指针使得快指针走到尾的时候与慢指针之间的差距恰好是k个节点那么此时的慢指针就是题中要求的节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k){struct ListNode* slowhead,*fasthead;while(k--){fastfast-next;}while(fast){slowslow-next;fastfast-next;}return slow-val;
}二、链表的回文结构
链表的回文结构_牛客题霸_牛客网 回文结构即使对称的本题思路是先利用快慢指针找到中间节点之后再从中间节点开始逆置此节点之后的链表得到一条新的链表之后再从原本的链表的头节点和这条新链表的头节点开始一一比较若是val值都相同则说明这个链表是回文结构
当链表是奇数个时新链表多出一个节点但是不影响代码的正常运行因为原链表中中间节点的前一个节点的指向还是新链表中作为尾节点的之前的中间节点新链表的倒数第二个指针指向的也是这个节点所以最后一次循环的时候其实是同一个节点在比较。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:bool chkPalindrome(ListNode* A) {// write code here//找到中间节点ListNode* slowA;ListNode* fastA;while(fast fast-next){slowslow-next;fastfast-next;}ListNode* midslow;//对从中间节点向后的节点组成的链表进行逆置操作ListNode* newheadNULL;ListNode* curmid; while(cur){ListNode* nextcur-next;cur-nextnewhead;newheadcur;curnext;}//开始从头比较若是都相等那么就是回文结构ListNode* headA;while(head newhead){if(head-val!newhead-val){return false;}headhead-next;newheadnewhead-next;}return true;}
};
三、相交链表
. - 力扣LeetCode 本题思路首先判断两条链表是否相交只需要判断尾节点的地址是否相同就行了因为当两条链表相交时无论从哪个节点开始相交起尾节点的地址一定相同反之若是尾节点的地址不相同那么这两条链表一定不相交
在已经知道了两条链表相交的情况下如何寻找开始相交的节点先计算出两条链表的长度再计算出长度差之后让长的链表先走这个长度差的节点此时长的链表和短的链表之后的节点个数就相同了此时开始一起遍历长链表和短链表在遍历过程中若长链表和短链表的某一个节点的地址相同就跳出循环此时的节点就是开始相交的节点
注意本题的比较不能用val值因为两条链表中不同的地址的节点可能含有相同的val值这时会造成混淆。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if(headANULL || headBNULL){return NULL;}struct ListNode* tailAheadA;struct ListNode* tailBheadB;int lenA1;int lenB1;while(tailA-next){tailA tailA-next;lenA;}while(tailB-next){tailB tailB-next;lenB;}if(tailA!tailB){return NULL;}int gapabs(lenA-lenB);struct ListNode* longlistheadA;struct ListNode* shortlistheadB;//先假设A更长if(lenBlenA){longlistheadB;shortlistheadA;}//若是B长就进入该语句改变更长链表指向的对象反之则假设成立while(gap--){longlistlonglist-next;}while(longlist ! shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}
