铅笔小新z个人主页博客专栏数据结构滴水不绝可穿石步履不休能至渊。一、链表1.1 链表算法OJ题1返回倒数第k个节点解题思路首先这道题我们可以用快慢指针的方法来做如图先让快慢指针都指向第一个节点然后让fast指针先走k步再让slow和fast一起走直到fast指针走到空此时slow指向的链表就是倒数第k位。参考代码struct ListNode* slow , *fast; slow fast head; while(k--) { fast fast-next; } while(fast) { slow slow-next; fast fast-next; } return slow-val;1.2 链表算法OJ题2判断一个链表是否为回文结构解题思路判断是否为回文结构我们可以找到中间节点将中间节点即以后的节点进行倒置然后将原链表的头节点与倒置后的头节点进行逐一比较如果链表总个数为奇数则循环结束条件是原链表走到空如果链表总个数是偶数则循环结束条件是两个链表一起走到空。寻找中间节点和将链表倒置都在我上一篇文章中参考代码typedef struct ListNode ListNode; ListNode* FindMid(ListNode* head) { ListNode* slow, *fast; slow fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; } return slow; } ListNode* Reverse(ListNode* mid) { ListNode* n1, *n2, *n3; n1 NULL, n2 mid, n3 n2-next; while(n2) { n2-next n1; n1 n2; n2 n3; if(n3) n3 n3-next; } return n1; } bool isPail(struct ListNode* head ) { ListNode* mid FindMid(head); ListNode* rmid Reverse(mid); while(head rmid) { if(head-val ! rmid-val) return false; head head-next; rmid rmid-next; } return true; }1.3 链表算法OJ题3相交链表解题思路首先我们可以判断两个链表是否相交遍历两个链表如果最后一个节点一样就说明两者相交反之则不相交。接下来判断在哪里相交我们可以从两个链表的同一位置进行遍历然后一直遍历到第一个相交的节点再返回从而解决问题。那么怎么从两个链表的同一个位置进行遍历呢我们可以分别算出两个链表的长度再进行相减从而得到长度差(gap)再让长的链表向后移动gap步再让两者同时向后进行遍历。参考代码typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode* curA headA, *curB headB; int lenA 0, lenB 0; while(curA-next) { curA curA-next; lenA; } while(curB-next) { curB curB-next; lenB; } if(curA ! curB) return NULL; int gap abs(lenA - lenB); ListNode* longlist headA, *shortlist headB; if(lenA lenB) { longlist headB; shortlist headA; } while(gap--) { longlist longlist-next; } while(longlist shortlist) { if(longlist shortlist) return longlist; longlist longlist-next; shortlist shortlist-next; } return longlist; }1.4 链表算法OJ题4环形链表解题思路我们可以用快慢指针慢指针一次走一步快指针一次走两步如果是环形链表的话快指针先进入循环然后一直在环形链表中走直到快指针遇到慢指针证明链表是环形链表。参考代码typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* slow head, *fast head; while(fast fast-next) { slow slow-next; fast fast-next-next; if(slow fast) return true; } return false; }