精华内容
下载资源
问答
  • java快慢指针

    2020-10-12 17:06:31
    创建环形列表 //创建一个环形的单向链表 class CircleSingleLinkedList { // 创建一个first节点,当前没有编号 private Boy first ... } 快慢指针的应用三 (寻找链表的中间结点): 快慢的指针应用四 ( 寻找重复数 ):

    创建环形列表

    //创建一个环形的单向链表
    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;
        }
    

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

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

    展开全文
  • Java快慢指针

    2021-08-14 19:46:41
    Java实现链表取中间值和判断链表是否有环问题 package linkList; /** * @Author zhw * Version 1.0 * @Description FastSlowTest * Date 2021/8/14 12:31 **/ public class FastSlowTest { //结点类 private...

    Java实现链表取中间值和判断链表是否有环问题

    package linkList;
    
    /**
     * @Author zhw
     * Version 1.0
     * @Description FastSlowTest
     * Date 2021/8/14 12:31
     **/
    public class FastSlowTest {
        //结点类
        private static class Node<T> {
            //存储数据
            T item;
            //下一个结点
            Node next;
            public Node(T item,Node next) {
                this.item = item;
                this.next = next;
            }
        }
    
        public static void main(String[] args) {
            Node<String> node1=new Node<>("a",null);
            Node<String> node2=new Node<>("b",null);
            Node<String> node3=new Node<>("c",null);
            Node<String> node4=new Node<>("d",null);
            Node<String> node5=new Node<>("e",null);
            Node<String> node6=new Node<>("f",null);
            Node<String> node7=new Node<>("g",null);
            //完成节点之间的指向
            node1.next=node2;
            node2.next=node3;
            node3.next=node4;
            node4.next=node5;
            node5.next=node6;
            node6.next=node7;
            //产生环
            node7.next=node4;
            //查找中间值
            //String mid = getMid(node1);
           // System.out.println("中间值为:"+mid);
            // 判断是否有环
           boolean circular = isCircular(node1);
           System.out.println("是否有环:"+circular);
        }
        /**
         * @Description: 快慢指针查询链表中间值
         * @param node node
         * @return: java.lang.String
        */
        public static String getMid(Node<String> node){
            Node<String> fast=node;
            Node<String> slow=node;
            while (fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
            }
            return slow.item;
        }
        /**
         * @Description: 判断链表中是否有环
         * @param node node
         * @return: boolean
        */
        public static boolean isCircular(Node<String> node){
            Node<String> fast=node;
            Node<String> slow=node;
            while (fast!=null&&fast.next!=null){
                fast=fast.next.next;
                slow=slow.next;
                if (fast.equals(slow)){
                    return true;
                }
            }
            return false;
        }
    }
    
    
    展开全文
  • public boolean hasCycle(ListNode head) { if(head==null) return false; ListNode fast = head; ListNode slow = head; while(1==1){ ...

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

    展开全文
  • 还有一种方式就是使用快慢指针的方式,定义两个指针,快指针速度是慢指针的两倍,这样同样的时间下,快指针的路程就是慢指针的两倍,也就是说,当快指针到最后的节点时,慢指针指向的就是中间节点,注意当节点数是...

    一、问题概述

    对于一个单向链表,要找到中间值的话,我们可以使用节点个数除以2的方式,然后循环N/2次来找到中间节点;
    还有一种方式就是使用快慢指针的方式,定义两个指针,快指针速度是慢指针的两倍,这样同样的时间下,快指针的路程就是慢指针的两倍,也就是说,当快指针到最后的节点时,慢指针指向的就是中间节点,注意当节点数是偶数的时候,指向的是中间部分的右边一个节点,当节点数为奇数时候,就是指向的中间节点。

    二、代码实现

    package mypackage;
    
    //测试
    public class MyJava {
        
        //节点类
        private static class Node<T> {
            T data;
            Node next;
    
            //构造方法
            public Node(T data, Node next) {
                this.data = data;
                this.next = next;
            }
        }
        //    查找中间值的方法,注意要到时候要传入第一个节点
        public static Integer getmid(Node node){
    //        定义快慢指针
            Node fast=node;
            Node slow=node;
    //        快指针不是null,且下一个节点也不是null的情况下
    //        让快指针每次走两步,慢指针每次走一步
    //        当快指针到最后的节点时,慢指针指向的就是中间节点
    //        注意当节点数是偶数的时候,指向的是中间部分的右边一个节点
    //        当节点数为奇数时候,就是指向的中间节点
    //        思考1:为什么要(fast!=null)&&(fast.next!=null)两个判断条件
    //        思考2:为什么(fast!=null)要在前,(fast.next!=null)要在后
    //        思考3:为什么要&&,而不是使用&
            while((fast!=null)&&(fast.next!=null)){
    //        while((fast.next!=null)&&(fast!=null)){
    //            两个next就是模拟两步
                fast=fast.next.next;
                slow=slow.next;
            }
    //        跳出循环表示快指针到最后的节点了
            return (Integer) slow.data;
        }
    
        public static void main(String[] args) {
    //        创建节点,采用这样的方式创建
            Node<Integer> a=new Node<Integer>(1,null);
            Node<Integer> b=new Node<Integer>(2,null);
            Node<Integer> c=new Node<Integer>(3,null);
            Node<Integer> d=new Node<Integer>(4,null);
            Node<Integer> e=new Node<Integer>(5,null);
            Node<Integer> f=new Node<Integer>(6,null);
            Node<Integer> g=new Node<Integer>(7,null);
    
    //        节点指向性
            a.next=b;
            b.next=c;
            c.next=d;
            d.next=e;
            e.next=f;
            f.next=g;
    //        调用方法
            Integer mid=getmid(a);
            System.out.println("中间节点的数据为:"+mid);
        }
    }
    

    结果为4,确实是中间节点:
    在这里插入图片描述

    三、思考点

    • 思考1:为什么要(fast!=null)&&(fast.next!=null)两个判断条件
    • 思考2:为什么(fast!=null)要在前,(fast.next!=null)要在后
    • 思考3:为什么要&&,而不是使用&

    这几个问题要一起解答,在这之前了解一下什么是空指针异常?
    什么是空指针异常?

    • 所谓的指针,就是java中的对象的引用。比如String s;这个s就是指针
    • 所谓的空指针,就是指针的内容为空,比如上面的s,如果令它指向null,就是空指针
    • 所谓的空指针异常,就是一个指针是空指针,你还要去操作它,既然它指向的是空对象,它就不能使用这个对象的方法。比如上面的假如为null,你还要用s的方法,比如s.equals(String x);那么就会产生空指针异常。

    回到问题,因为fast步长为2,当节点数为奇数的时候,经过一定的次数,fast一定是在最后一个节点,然后经过(fast.next!=null)判断就会跳出循环,此时(fast!=null)确实是多余的;

    但是当节点数为偶数的时候,经过一定的次数,fast一定是在最后一个节点的后一个节点,什么意思呢,就是这个时候fast一定是移动到null的,那么此时还可以使用(fast.next!=null)判断吗,好像是可以的,但是并不可以,因为会出现NullPointerException错误,这个错误就是空指针异常,null.next是什么?对null调用任何方法都会造成NullPointerException错误。

    那么怎么办呢,只有一个办法,就是让(fast.next!=null)不执行,那么怎么判断循环结束呢,就需要使用(fast!=null)了,因此两个条件都是需要的,并且为了不出现NullPointerException错误,让(fast.next!=null)不执行,得使用&&与符号,这个符号当前一个条件为false时,直接就跳出循环了,不会再执行后一个条件,而单个&符号则不会有短短路的功能,即使前一个条件已经判断为false后一个条件还是会判断。另外使用&&时,(fast!=null)要在前,(fast.next!=null)要在后 ,这样当(fast!=null)条件能跳出循环的时候,(fast.next!=null)就不会再执行了,就不会出现NullPointerException了。

    错误案例1

    节点改为偶数个,只创建6个节点即可,判断条件改为(fast!=null)&(fast.next!=null),运行结果如下:
    在这里插入图片描述

    错误案例2

    节点改为偶数个,只创建6个节点即可,判断条件改为(fast.next!=null)&&(fast!=null),运行结果如下:
    在这里插入图片描述

    错误案例3

    节点改为偶数个,只创建6个节点即可,判断条件改为(fast.next!=null),运行结果如下:
    在这里插入图片描述

    展开全文
  • 给定一个链表,旋转链表,将链表...//快慢指针修改结点从而旋转链表 while(fast.next!=null) { fast=fast.next; slow=slow.next; } fast.next=head; ListNode reshead=slow.next; slow.next=null; return reshead; } }
  • * 思路是快慢指针法,通过判断两个节点是否==, * 即内存地址相同则证明链表有环存在 */ public class LinkedListCycle { /** * 给定一个链表,判断链表中是否有环。 * 为了表示给定链表中的环,我们使用整数...
  • } 使用快慢指针解法: 放置双指针 i 和 j,其中 i 是慢指针,j 是快指针,当两个指针所知数字相等时,就增加 j 来跳过重复项,i 保持不变。 当两个指针所指数字不同时,只需要增加 i ,并把 j 所指的数字复制给 i ...
  • 算法中快慢指针的应用(Java)

    千次阅读 2019-03-29 16:53:51
    何为快慢指针快慢指针就是指两个指针在移动的过程中,慢的指针每次移动一步,而快的指针每次移动两步。 快慢指针的应用一 (判断一个链表是否有环): 问题来源:leetcode-141题,环形链表 ...
  • 移动零 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非...思路:快慢指针java实现: class Solution { public void moveZeroes(int[] nums) { int slow = 0; for(int fast = 0;fast<.
  • /** * 双指针指向,快指针与目标值不同时间,改变慢指针的指向 * 注意快指针的速度,一次为一格 */ class Solution { public static void main(String[] args) { Solution solution = new Solution(); int[] ints =...
  • 给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。 测试样例: 1->2->2->1 返回:true import java.util.*; /* public class ListNode { int val; ...
  • 快慢指针检测链表是否有环 public class Test { //快慢指针检测链表是否有环 public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode fast = head; ListNode sl
  • java数据结构面试问题—快慢指针问题 上次我们学习了环形链表的数据结构,那么接下来我们来一起看看下面的问题,  判断一个单向链表是否是环形链表?   看到这个问题,有人就提出了进行遍历链表,记住第一元素...
  • 解决思路:设置两个指针,一个指针一次向前走一步(慢指针),另一个指针一次向前走两步(快指针)。若链表有环,则快指针一定可以追上慢指针;若链表无环,则会走到链表末端。 public class QuickSlowPointer { ...
  • 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有...
  • java单链表快慢指针

    2019-09-28 20:18:53
    快慢指针真香!不急还有一个例题 LeetCode141. 环形链表 这个是官方题解 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; *...
  • 快慢指针java

    2021-11-27 12:53:49
    文章目录前言一、快慢指针是什么?二、多种情况奇数一起走慢指针快一步快指针快一步(无意义)快指针快两步偶数一起走慢指针快一步快指针快一步快指针快两步 前言 快慢指针是链表的一个重要的方法,在面试中常常...
  • 利用快慢指针,思路如下:我们把一个链表看成一个跑道,假设a的速度是b的两倍,那么当a跑完全程后,b刚好跑一半,以此来达到找到中间节点的目的。 时间复杂度: O(N/2) 代码 public int search(Li...
  • 两个指针的移动速度一快一慢,一般情况下,快指针的移动步长为慢指针的两倍。 链表长度为奇数的情况下,快指针遍历完一遍链表,慢指针恰好在链表中间。 链表长度为偶数的情况下,快指针遍历完一遍链表,慢指针恰好在...
  • 快慢指针删除数组中为0的数 import java.util.Arrays; /** * @Name: 快慢指针删除数组中为0的数据 * @Author:ZYJ * @Date:2019-09-02-20:03 * @Description: */ public class DeleteZero { public static ...
  • * 思路是快慢指针法,通过判断两个节点是否==, * 即内存地址相同则证明链表有环存在 *返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 */ public class LinkedListCycle02 { /** * @param head ...
  • 拿到这道题首先想到的是找中间节点,所以肯定是用快慢指针,然后应该把前面或者后面倒叙再去比。 就想到反转链表这个题,进阶要求说是空间复杂度O(1)所以不能用栈,于是重新想了一下反转链表的做法,这里也是看了...
  • 思路:双指针法 使用快慢指针,i为慢指针,j为快指针。初始状态下i=0,j从下标为1出开始向后移动。如果nums[i]=nums[j],就增加j的值跳过重复项。如果muns[i]!=nums[j],就把nums[j]的值赋值给nums[i+1],并且递增i。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,926
精华内容 3,170
关键字:

java快慢指针

java 订阅