一、返回倒数第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;
}
