算法思路

如果链表存在环，那么计算出环的长度n，然后准备两个指针pSlow，pFast，pFast先走n步，然后pSlow和pFase一块走，当两者相遇时，即为环的入口处；所以解决三个问题：如何判断一个链表有环；如何判断链表中环的大小；链表中环的入口结点。实际上最后的判断就如同链表的倒数第k个节点。

代码如下

Copy
public class Solution {     public ListNode EntryNodeOfLoop(ListNode pHead)     {         if(pHead.next == null || pHead.next.next == null)             return null;         ListNode slow = pHead.next;         ListNode fast = pHead.next.next;         while(fast != null){             if(fast == slow){                 fast = pHead;                 while(fast != slow){                     fast = fast.next;                     slow = slow.next;                 }                 return fast;             }             slow = slow.next;             fast = fast.next.next;         }         return null;     } } 

以上5题的套路其实都非常类似，第5题可以说是前面几道题的一个汇总题目吧，链表类的题利用快慢指针，两个指针确实挺多的，如下面题目7

6.单链表在时间复杂度为O(1)删除链表结点

问题描述

给定单链表的头指针和一个结点指针，定一个函数在时间复杂度为O(1)删除链表结点

算法思路

根据了解的条件，如果只有一个单链表的头指针，链表的删除操作其实正常的是O（n）的时间复杂度。因为首先想到的是从头开始顺序遍历单链表，然后找到节点，再进行删除。但是这样的方式达到的时间复杂度并不是O（1）；实际上纯粹的删除节点操作，链表的删除操作是O（1）。前提是需要找到删除指定节点的前一个结点就可以。

那么是不是必须找到删除指定节点的前一个结点呢？如果我们删除的节点是A，那么我们把A下一个节点B和A的data进行交换，然后我们删除节点B，是不是也可以达到同样的效果。

答案是肯定的。
既然不能在O(1)得到删除节点的前一个元素，但我们可以轻松得到后一个元素，这样，我们何不把后一个元素赋值给待删除节点，这样也就相当于是删除了当前元素。可见，该方法可行，但如果待删除节点为最后一个节点，则不能按照以上思路，没有办法，只能按照常规方法遍历，时间复杂度为O(n)，是不是不符合题目要求呢？可能很多人在这就会怀疑自己的思考，从而放弃这种思路，最后可能放弃这道题，这就是这道面试题有意思的地方，虽看简单，但是考察了大家的分析判断能力，是否拥有强大的心理，充分自信。其实我们分析一下，仍然是满足题目要求的，如果删除节点为前面的n-1个节点，则时间复杂度为O(1)，只有删除节点为最后一个时，时间复杂度才为O(n)，所以平均的时间复杂度为：（O(1) * (n-1) + O(n)）/n = O(1);仍然为O(1).

代码如下

Copy
/* Delete a node in a list with O(1)  * input:    pListHead - the head of list  *            pToBeDeleted - the node to be deleted  */  struct  ListNode   {     int            m_nKey;     ListNode*    m_pNext; };  void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted) {     if (!pListHead || !pToBeDeleted)         return;          if (pToBeDeleted->m_pNext != NULL) {          ListNode *pNext = pToBeDeleted->m_pNext;         pToBeDeleted->m_pNext = pNext->m_pNext;         pToBeDeleted->m_nKey = pNext->m_nKey;          delete pNext;         pNext = NULL;     }     else { //待删除节点为尾节点         ListNode *pTemp = pListHead;         while(pTemp->m_pNext != pToBeDeleted)              pTemp = pTemp->m_pNext;         pTemp->m_pNext = NULL;          delete pToBeDeleted;         pToBeDeleted = NULL;     } }

题目的考虑的点，也很特别

7.两个链表的第一个公共结点

问题描述

输入两个单链表，找出他们的第一个公共结点。

算法思路

我们了解到单链表的指针是指向下一个节点的，如果两个单链表的第一个公共节点就说明他们后面的节点都是在一起的。类似下图，由于两个链表的长度可能是不一致的，所以首先比较两个链表的长度m，n，然后用两个指针分别指向两个链表的头节点，让较长的链表的指针先走|m-n|个长度，如果他们下面的节点是一样的，就说明出现了第一个公共节点。

代码如下

Copy
 /* public class ListNode {     int val;     ListNode next = null;       ListNode(int val) {         this.val = val;     } }*/ public class 
                        
关键字：