数据结构---链表经典OJ

1.输入一个链表输出该链表中倒数第k个结点。快慢指针 注意要分奇偶数int kthToLast(struct ListNode* head, int k) { struct ListNode *fast head, *slow head; //快指针先走K步 while(k--){ fastfast-next; } //同时走 while(fast){ slowslow-next; fastfast-next; } return slow-val; }2.链表的回文结构#include memory class PalindromeList { public: struct ListNode* middleNode(struct ListNode* head) { // 创建快慢指针 ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } //此时slow刚好指向的就是中间节点 return slow; } struct ListNode* reverseList(struct ListNode* head) { //判空 if (head NULL) { return head; } //创建三个指针 ListNode* n1, *n2, *n3 NULL; n1 NULL, n2 head, n3 n2-next; while (n2) { n2-next n1; n1 n2; n2 n3; if (n3) { n3 n3-next; } } return n1; } bool chkPalindrome(ListNode* A) { // write code here struct ListNode* mid middleNode(A); struct ListNode* rmid reverseList(mid); while (rmid A) { if (rmid-val ! A-val) { return false; } rmid rmid-next; A A-next; } return true; } };3.相交链表题目160. 相交链表 - 力扣LeetCode解题思路A链表的节点依次跟B链表所有节点比较A链表某个节点跟B链表某个节点相等这个节点就是交点1.判断是否相交跟判断尾指针注意需要用地址的判断2.若相交找出第一个交点struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { struct ListNode *curA headA, *curB headB; int lenA0,lenB0; while(curA-next){ curAcurA-next; lenA; } while(curB-next){ curBcurB-next; lenB; } //尾节点不相等就是不相交 if(curA!curB){ return NULL; } //长的先走差距步再同时走第一个相等就是交点 //假设法 int gapabs(lenA-lenB); struct ListNode*longListheadA,*shortListheadB; if(lenBlenA){ longListheadB; shortListheadA; } while(gap--){ longListlongList-next; } while(longList!shortList){ longListlongList-next; shortListshortList-next; } return shortList; }3.带环链表题目141. 环形链表 - 力扣LeetCodebool hasCycle(struct ListNode* head) { struct ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }3.2.142. 环形链表 II - 力扣LeetCodestruct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow head; struct ListNode *fast head; // 1. 判断是否有环 while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; // 快慢指针相遇说明有环 if (slow fast) { // 2. 寻找入环的第一个节点 struct ListNode *index1 head; // 从头开始 struct ListNode *index2 slow; // 从相遇点开始 // 两个指针每次走一步直到相遇 while (index1 ! index2) { index1 index1-next; index2 index2-next; } // 相遇点即为入环点 return index1; } } // 如果跳出循环说明 fast 遇到了 NULL无环 return NULL; }