c语言快慢指针,JAVA 指针

创建环形列表

//创建一个环形的单向链表class CircleSingleLinkedList {// 创建一个first节点，当前没有编号private Boy first = null;// 添加节点，构建成一个环形链表public void addBoy(int nums) {// 对nums做一个校验if (nums < 1) {System.out.println("数据错误");return;}// 定义辅助节点Boy curBoy = null;// 使用循环创建环形链表for (int i = 1; i <= nums; i++) {// 根据编号创建节点Boy boy = new Boy(i);// 如果是第一个节点if (i == 1) {first = boy;first.setNext(first);curBoy = first;// 让curBoy指向第一个节点，帮助构建链表} else {curBoy.setNext(boy);boy.setNext(first);// 使其指向第一个节点，形成环状curBoy = boy;// curBoy后移}}}// 遍历当前环形链表public void list() {// 判断链表是否空if (first == null) {System.out.println("链表为空");return;}// 定义辅助节点Boy curBoy = first;while (true) {System.out.println("节点编号:" + curBoy.getNo());if (curBoy.getNext() == first) {// 此时说明遍历完毕break;}curBoy = curBoy.getNext();// curBoy后移}}}//创建一个Boy类，表示一个节点class Boy {private int no;// 编号private Boy next;// 指向下一个节点public Boy(int no) {this.no = no;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}}

判断单链表是否为循环链表
无奈的春天：在这道题中，我首先想到的办法也是哈希表。遍历所有的结点，并在哈希表中存储每个结点的引用。若当前结点为空结点，则返回null，表示该单链表中没有环。若发现当前结点已经存在于哈希表中，则返回true。这种方法的时间复杂度和空间复杂度均为O(n)。

public static boolean hasCycle(Boy head) { Set<Boy> seen = new HashSet<Boy>(); while (head != null) { if (!seen.add(head)) { return true; } head = head.getNext(); } return false; }

解法二：快慢指针法，想像两个长跑运动员在赛跑，若跑道中存在环，则快的长跑员一定会追上慢的长跑员。因此，使用两个指针，一个fast，一个slow，判断条件即为当 fast == slow时，返回true，表示有环。否则，当fast == null时，则返回null，此时快指针已经为null，表示不存在环。该方法的时间复杂度为O(n),空间复杂度为O(1)。

public static boolean hasCycle(ListNode head) { ListNode slow = head; if(slow == null) return false; ListNode fast = head.next; while(fast != null && fast.next != null){ if(slow == fast) return true; slow = slow.next; fast = fast.next.next; } return false; }

快慢指针的应用二 (找到有环链表的切入结点)：
https://blog.csdn.net/hudaJY/article/details/88895355

public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; boolean ifhas = false; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(fast == slow) { ifhas = true; break; } } if(!ifhas) return null; while(head != slow) { head = head.next; slow = slow.next; } return head; }

快慢指针的应用三 (寻找链表的中间结点)：

快慢的指针应用四 ( 寻找重复数 )：