链表算法经典十题总结 (2)

代码如下：

/** * 判断单链表是否存在环 * @param head * @return */ public static <T> boolean isLoopList(ListNode<T> head){ ListNode<T> slowPointer, fastPointer; //使用快慢指针，慢指针每次向前一步，快指针每次两步 slowPointer = fastPointer = head; while(fastPointer != null && fastPointer.next != null){ slowPointer = slowPointer.next; fastPointer = fastPointer.next.next; //两指针相遇则有环 if(slowPointer == fastPointer){ return true; } } return false; } 4.链表中环的大小 问题描述

有一个单向链表，链表当中有可能出现“环”，那么如何知道链表中环的长度呢？

算法思路

由可以知道，快慢指针可以找到链表是否有环存在，如果两个指针第一次相遇后，第二次相遇是什么时候呢？第二次相遇是不是可以认为快的指针比慢的指针多跑了一个环的长度。所以找到第二次相遇的时候就找到了环的大小。

代码如下 //求环中相遇结点 public Node cycleNode(Node head){ //链表为空则返回null if(head == null) return null; Node first = head; Node second = head; while(first != null && first.next != null){ first = first.next.next; second = second.next; //两指针相遇，则返回相遇的结点 if(first == second) return first; } //链表无环，则返回null return null; } public int getCycleLength(Node head){ Node node = cycleNode(head); //node为空则代表链表无环 if(node == null) return 0; int length=1; Node current = node.next; //再次相遇则循环结束 while(current != node){ length++; current = current.next; } return length; } 5.链表中环的入口结点 问题描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

算法思路

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

代码如下 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).

代码如下 /* 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.两个链表的第一个公共结点 问题描述

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

算法思路