精华内容
下载资源
问答
  • 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;
        }
    

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

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

    展开全文
  • 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;
                }
                }
                
            }

    展开全文
  • 给定一个链表,旋转链表,将链表...//快慢指针修改结点从而旋转链表 while(fast.next!=null) { fast=fast.next; slow=slow.next; } fast.next=head; ListNode reshead=slow.next; slow.next=null; return reshead; } }

    给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

    示例 1:
    
    输入: 1->2->3->4->5->NULL, k = 2
    输出: 4->5->1->2->3->NULL
    解释:
    向右旋转 1: 5->1->2->3->4->NULL
    向右旋转 2: 4->5->1->2->3->NULL
    示例 2:
    
    输入: 0->1->2->NULL, k = 4
    输出: 2->0->1->NULL
    解释:
    向右旋转 1: 2->0->1->NULL
    向右旋转 2: 1->2->0->NULL
    向右旋转 3: 0->1->2->NULL
    向右旋转 4: 2->0->1->NULL
    
    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/rotate-list
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            ListNode fast=head;
            ListNode slow=head;
            int cnt=0;
            while(fast!=null)
            {//得到链表长度
                fast=fast.next;
                cnt++;
            }
            if(cnt==0) return head;
            else k%=cnt;
            fast=head;
            for(int i=0;i<k;i++) fast=fast.next;//快慢指针修改结点从而旋转链表
            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 { /** * 给定一个链表,判断链表中是否有环。 * 为了表示给定链表中的环,我们使用整数...
    /**
     * 判断一个链表是否有环,
     * 思路是快慢指针法,通过判断两个节点是否==,
     * 即内存地址相同则证明链表有环存在
     */
    public class LinkedListCycle {
    
        /**
         * 给定一个链表,判断链表中是否有环。
         * 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
         * 如果 pos 是 -1,则在该链表中没有环。
         * 示例 1:
         * 输入:head = [3,2,0,-4], pos = 1
         * 输出:true
         * 解释:链表中有一个环,其尾部连接到第二个节点。
         * 示例 2:
         * 输入:head = [1,2], pos = 0
         * 输出:true
         * 解释:链表中有一个环,其尾部连接到第一个节点。
         * 示例 3:
         * 输入:head = [1], pos = -1
         * 输出:false
         * 解释:链表中没有环。
         * 来源:力扣(LeetCode)
         * 链接:https://leetcode-cn.com/problems/linked-list-cycle
         * 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
         * @param head 链表的头
         * @return 是否有环
         */
        public static boolean hasCycle(ListNode head){
            if(head == null || head.next == null){
                return false;
            }
            //慢指针
            ListNode slow = head;
            //快指针
            ListNode fast = head;
            while(fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                    return true;
                }
            }
            return false;
        }
    
        public static void main(String[] args){
            //案例一
            ListNode head = new ListNode(3);
            ListNode head1 = new ListNode(2);
            ListNode head2 = new ListNode(0);
            ListNode head3 = new ListNode(-4);
            head.next = head1;
            head1.next = head2;
            head2.next = head3;
            head3.next = head2;
            System.out.println(hasCycle(head));
            //案例二
            ListNode node  = new ListNode(1);
            ListNode node1  = new ListNode(2);
            node.next = node1;
            node1.next = node;
            System.out.println(hasCycle(node));
            //案例三
            ListNode list = new ListNode(1);
            System.out.println(hasCycle(list));
        }
    }
    
    
    
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    

     

    展开全文
  • 还有一种方式就是使用快慢指针的方式,定义两个指针,快指针速度是慢指针的两倍,这样同样的时间下,快指针的路程就是慢指针的两倍,也就是说,当快指针到最后的节点时,慢指针指向的就是中间节点,注意当节点数是...
  • * 思路是快慢指针法,通过判断两个节点是否==, * 即内存地址相同则证明链表有环存在 *返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 */ public class LinkedListCycle02 { /** * @param head ...
  • // 快指针不是null,且下一个节点也不是null的情况下 // 让快指针每次走两步,慢指针每次走一步 // 如果快慢指针能相遇,那么就证明链表是环形的 while((fast!=null)&&(fast.next!=null)){ // 两个next就是模拟两步 ...
  • java单链表快慢指针

    2019-09-28 20:18:53
    快慢指针真香!不急还有一个例题 LeetCode141. 环形链表 这个是官方题解 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; *...
  • 快慢指针 求中间节点 package com.link; import java.awt.print.Printable; import java.util.ArrayList; import java.util.List; public class Solution { /** * @param head: the given linked list * @...
  • 今天学习数据结构快速排序时发现网上有很多种快速排序的方法,于是我选择了算法导论上面一种比较标准的快慢指针的方法实现了. 实现思路来自b站: https://www.bilibili.com/video/av47837026 import java.util....
  • 快慢指针: 快指针找终点,慢指针反转前半个链表 快指针回到慢指针的位置(中点,记得进行奇偶判断) 此刻,链表已经被分成两条以slow、fast开始的链表,遍历对比即可 /** * Definition for singly-linked list....
  • /** * 双指针指向,快指针与目标值不同时间,改变慢指针的指向 * 注意快指针的速度,一次为一格 */ class Solution { public static void main(String[] args) { Solution solution = new Solution(); int[] ints =...
  • 算法中快慢指针的应用(Java)

    千次阅读 2019-03-29 16:53:51
    何为快慢指针快慢指针就是指两个指针在移动的过程中,慢的指针每次移动一步,而快的指针每次移动两步。 快慢指针的应用一 (判断一个链表是否有环): 问题来源:leetcode-141题,环形链表 ...
  • 常见题,用上了久违的快慢指针 思路 & 代码 举个例子就能明白了: 我和汽车,进行一场比赛,跑道可能是环形跑道,也可能是直道。 直道的话,将会以汽车撞到终点为结束( fast == null),也就是非环 弯道的话...
  • 快慢指针可以判断出链表是否为环链表,网上此类文章比较多,可以查阅相关实现,同时快慢指针也能找出环链表的入口。 上图是一个环链表,当快慢指针(快指针步长没有限制,慢指针为1)相遇时,我们可以判断到列表中有...
  • 因为这题给了限定 有序,O(1) 不能改变数组换成新的 所以用快慢指针就行 package suanfa.快慢指针; /** * 因为这题给了限定 有序,O(1) 不能改变数组换成新的 所以用快慢指针就行 */ public class ZhiZhen { ...
  • 快慢指针检测链表是否有环 public class Test { //快慢指针检测链表是否有环 public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode fast = head; ListNode sl
  • JAVA刷Leecode-玩转双指针-快慢指针(142)算法思想内容分类环形链表 II(142,medium)题目描述输入输出样例示例1示例2解题思路1:题解1解题思路2:题解2解题思路3:题解3解题思路4:题解4资源学习 算法思想 双指针...
  • 声明两个指针,分别为快指针和慢指针。当快指针到达链尾的时候,有两种情况,分别为fast指向最后一个元素(链表为偶数),此时中间元素为slow.next;当fast指向的是倒数第二个元素的时候(链表为奇数),也为slow.next....
  • 快慢指针: 计算两个数组的长度差,然后将较长数组的指针移动到与较短数组相等,然后一起走,相等时即为相交节点 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode ...
  • //判断是否有环,快指针走两步,满指针走一步,如果有环,两个指针会相遇 public static boolean isRing(PointerBean root) { if (root == null) { return false; } PointerBean fast ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 457
精华内容 182
关键字:

java快慢指针

java 订阅