牛客算法训练-判断链表是否有环

题目描述

将给出的链表中的节点每\ k k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是\ k k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 \ O(1) O(1)
例如：
给定的链表是1\to2\to3\to4\to51→2→3→4→5
对于 \ k = 2 k=2, 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5
对于 \ k = 3 k=3, 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5

解题思路

这道题我一开始解的时候想的是遍历一下，判断当前节点是否是环节点（也就是链表环开始的节点）但是一直报超时，想不清，看了一下别人的解题思路
发现大部分用的是快慢指针来解的，

这是带环链表其中的值为6的节点就是是我自称的环节点

设置两个指针，一个指针一次走一步，另一个指针一次走两步,如果两个指针相遇的话，那这个链表就是有环的，这个解法时间复杂度 ***O(n)***,额外空间复杂度***O(1)***。 至于为甚么会相遇，看别人的动图就好，图解的很清楚

代码实现

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
          if(head==null)
            return null;
        int count=0;
        ListNode virtualRoot = new ListNode(0);
        virtualRoot.next = head;
        ListNode pre = virtualRoot;
        ListNode temp, start = pre.next;
        while(head!=null){
            count++;
            head=head.next;
        }
        for(int i=0;i<count/k ;i++){
            for(int j=1;j<k;j++){
                temp=start.next;
                start.next=temp.next;
                temp.next=pre.next;
                pre.next=temp;
            }
            pre=start;
            start=start.next;
        }
        return virtualRoot.next;
    }
}