目录
一、找出并返回链表的中间结点
二、输出链表中倒数第k个结点
三、判断链表中是否有环
四、两个单链表相交
一、找出并返回链表的中间结点
给你单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
要求：只遍历一遍链表
可以使用快慢指针：fast 一次走两步，slow 一次走一步。当 fast == NULL（偶数个结点）或者 fast->next == NULL（奇数个结点）就停止，返回 slow。
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* slow, *fast; slow = fast = head; while(fast && fast->next){slow = slow->next; fast = fast->next->next;}return slow;
}
注意：
1、一次性定义多个指针时，第二个及以后的指针名前面都要加 * 。
2、while（ ）括号内是循环继续的条件。
二、输出链表中倒数第k个结点
输入一个链表,输出该链表中倒数第k个结点。
要求：只遍历一遍链表
快慢指针：fast 先走 k - 1 步，然后 fast 和 sliow 同时走，直到 fast 走到链表的最后一个结点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* slow, *fast; slow = fast = pListHead;while(--k){fast = fast->next;}while(fast->next){slow = slow->next; fast = fast->next;}
}三、判断链表中是否有环
给你一个链表的头节点 head ，判断链表中是否有环。
使用快慢指针：fast 一次走两步，slow 一次走一步。
bool hasCycle(struct ListNode *head)
{ if(head == NULL)return false;if(head->next == NULL)return false;struct ListNode * slow = head;struct ListNode * fast = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow)return true;}return false;
}注意循环的条件是 fast != NULL && fast->next != NULL。
四、两个单链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
要求：时间复杂度O(n)，空间复杂度O(1)。
思路：1、分别求两个链表的长度 2、长的链表先走 差距步 3、同时走，第一个地址的结点相同就是交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* tailA = headA, *tailB = headB; int lenA = 1, lenB = 1; while(tailA->next){tailA = tailA->next; ++lenA;}while(tailB->next){tailB = tailB->next; ++lenB;}if(tailA != tailB)return NULL;int gap = abs(lenA-lenB); struct ListNode* longList = headA, *shortList = headB; if(lenA ‹ lenB){longList = headB; shortList = headA;}while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next; shortList = shortList->next;}return longList;}
