精华内容
下载资源
问答
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 说明:不允许修改给定的链表。进阶: 你能否不使用额外空间解决此题? 解题思路 无环链表,最后一个节点为nil,有环链表可以无限循环...

    题目描述

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

    说明:不允许修改给定的链表。
    进阶:

    你能否不使用额外空间解决此题?

    解题思路

    • 无环链表,最后一个节点为nil,有环链表可以无限循环next下去
    • 不用额外空间:快慢节点,慢节点一次走一步,快节点一次走两步,当进入环中,每次循环,快节点会离慢节点近一步,快节点最终会追上慢节点
    • 用额外空间: 用map存走过的节点,第一个走过的节点就是环的入口
    • 不用额外空间

    环形链表

    设:链表头是X,环的第一个节点是Y,slow和fast第一次的交点是Z。各段的长度分别是a,b,c,如图所示
    第一次相遇时slow走过的距离:a+b,fast走过的距离:a+b+c+b
    因为fast的速度是slow的两倍,所以fast走的距离是slow的两倍,有 2(a+b) = a+b+c+b,可以得到a=c(这个结论很重要!)
    这时候,slow从X出发,fast从Z出发,以相同速度走,同时到达Y,Y就是环的入口,即第一个节点

    代码实现

    // ListNode Definition for singly-linked list.
    type ListNode struct {
        Val  int
        Next *ListNode
    }
    
    func detectCycle(head *ListNode) *ListNode {
        if head != nil {
            slow := head
            fast := head
            for fast != nil && fast.Next != nil {
                slow = slow.Next
                fast = fast.Next.Next
                if slow == fast {
                    // X---------Y---------Z
                    //x起点,y环的起点,z是相遇点
                    //链表头是X,环的第一个节点是Y,slow和fast第一次的交点是Z。各段的长度分别是a,b,c
                    //相遇时,fast走过的距离为 2(a+b)=a+b+c+b,得到距离a=c
                    //则 slow从head开始走,fast从Z点开始走,速度都是一次走一步,slow和fast同时到达Y点,即环的入口
                    slow = head
                    for slow != fast {
                        slow = slow.Next
                        fast = fast.Next
                    }
                    return slow
                }
            }
        }
        return nil
    }

    GitHub

    • 源码传送门
    • 项目中会提供各种数据结构及算法的Golang实现, LeetCode解题思路及答案
    题目来源

    leetcode 142. 环形链表 II

    展开全文
  • 本文主要是记录了LeetCode中的一些链表题目,并给出了不同的方法来解决这些题目。本文涉及的链表的题目有:反转链表,环形链表,交换链表的节点,K个一组翻转链表

    数组和链表

    提及数组和链表。习惯性地就想起了数组的查找是O(1)、平均插入和删除的时间复杂度为O(N)。链表查找是O(N)、插入和删除是O(1)。

    仔细想想,这样的说法并不完全正确。这里的查找是说根据下标来查找,而不是查找根据元素值来进行查找。比如有个数组,a[ ],访问数组的第三个元素(下标从0开始),直接用a[2]就可以得到第三个元素,而链表的话并不支持这样的快速访问,你要得到第三个元素,必须一个一个遍历,需要一直数到第三个元素。原因在于,数组的地址是连续的,我们知道第一个元素的地址:base。知道数组中元素的大小:size,比如一个int占4个字节。然后就可以通过这么一个计算公式得到第k个元素的地址:base + (k - 1)size 然后就可以进行访问。而链表的存储空间并不连续,所以无法这样计算。

    也就是说:根据下标来查找,数组的时间复杂度为O(1),链表为O(N)

    如果不是根据下标来查找,而是根据值来查找呢?也就是说我们不是要找第三个元素,而是要找有没有3这个元素。那不好意思,数组和链表的时间复杂度都是O(N),因为必须得从头开始遍历,一个一个找。如果数组中的元素是有序的,那么可以用二分查找,时间复杂度可以降低为O(logn),但是达不到O(1)。如果链表中的元素也是有序的呢,可以用跳表这种数据结构,用空间换时间,也可以将查找的时间复杂度降低为O(logn)。

    那有没有一种数据结构,根据元素值来进行查找可以达到O(1)的时间复杂度呢,目前我所了解的算法里面只有Hash表能达到这样的效果,而且还得看Hash函数是否设计得好。

    本篇设计到的题目

    LeetCode206. 反转链表

    LeetCode141. 环形链表

    LeetCode24. 两两交换链表中的节点

    LeetCode142. 环形链表 II

    LeetCode25. K 个一组翻转链表

    链表题目练习(包含代码)

    ListNode节点的定义以及相应的操作方法

    为了方便在本机调试,我还写了一些方法用于生成链表返回链表中的第K个节点返回链表的遍历结果。为了简单,我也没使用泛型,假设链表中存储的都是int类型的数据。

    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 链表的定义
     * @author simon zhao
     */
    public class ListNode {
      int val;
      ListNode next;
    
      public ListNode(int val) {
        this.val = val;
      }
    
      /**
       * 根据数组生成LinkedList
       *
       * @param nums
       * @return
       */
      public static ListNode generateLinkedList(int[] nums) {
        if (nums == null || nums.length == 0) {
          return null;
        }
        ListNode head = new ListNode(nums[0]);
        ListNode cur = head;
        for (int i = 1; i < nums.length; ++i) {
          ListNode node = new ListNode(nums[i]);
          cur.next = node;
          cur = node;
        }
        return head;
      }
    
      /**
       * 遍历LinkedList,返回一个List<Integer>
       *
       * @param head
       * @return
       */
      public static List<Integer> traverseLinkedList(ListNode head) {
        if (head == null) {
          return null;
        }
        List<Integer> traverse = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
          traverse.add(cur.val);
          cur = cur.next;
        }
        return traverse;
      }
    
      /**
       * 返回LinkedList中index这个ListNode
       *
       * @param head
       * @param index
       * @return
       */
      public static ListNode getIndexNode(ListNode head, int index) {
        if (head == null) {
          return null;
        }
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
          if (count == index) {
            return cur;
          }
          if (count < index) {
            count++;
            cur = cur.next;
          }
        }
        //如果LinkedList都已经遍历完毕,但是count依然小于index,说明index过大,超出了LinkedList的长度
        return null;
      }
    }
    
    

    LeetCode206. 反转链表

    题目链接:LeetCode206. 反转链表

    题目概要

    反转一个单链表。

    示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

    一段精简的Python代码

    def reverseList(self, head):
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev
    

    需要注意的是:cur.next, prev, cur = prev, cur, cur.next并不是先进行cur.next = prev,然后进行prev = cur。而是多步赋值操作一起进行的,堪称一步到位。
    在这里插入图片描述
    用Java代码实现

    方法一:使用三个指针进行迭代

    public ListNode reverseList(ListNode head) {
       if (head == null) {
         return head;
       }
       ListNode cur = head, pre = null, next;
       while (cur != null) {
         next = cur.next;
         cur.next = pre;
         pre = cur;
         cur = next;
       }
       return pre;
     }
    

    方法二:使用递归

    public ListNode reverseList(ListNode head) {
      if (head == null || head.next == null) {
        return head;
      }
      ListNode p = reverseList(head.next);
      head.next.next = head;
      head.next = null;
      return p;
    }
    

    递归代码不好理解,可以看图
    在这里插入图片描述

    LeetCode141. 环形链表

    题目链接:LeetCode141. 环形链表

    题目概要

    给定一个链表,判断链表中是否有环。
    如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
    如果链表中存在环,则返回 true 。 否则,返回 false 。

    方法一:使用快慢指针

    采用快慢指针,快指针每次走两步,慢指针每次走一步,如果快慢指针能相遇,则说明有环。

     public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
          return false;
        }
        ListNode quick = head.next.next, slow = head;
        while (quick != slow) {
          if (quick == null || quick.next == null) {
            return false;
          }
          quick = quick.next.next;
          slow = slow.next;
        }
        return true;
      }
    

    虽然上面这段代码能通过LeetCode,但是逻辑有问题,应该将slow = head修改为slow = head.next。不然slow指针就起跑慢了。
    在这里插入图片描述

    方法二:暴力法

    暴力法。循环Integer.MAX_VALUE / 30次,若能发现null,则说明无环,在给定次数内,都没发现null,则认为是有环的,,该方法不一定准确,但是能通过LeetCode。

     public boolean hasCycle(ListNode head) {
        ListNode cur = head;
        for (int i = 0; i < Integer.MAX_VALUE / 30; ++i) {
          if (cur == null || cur.next == null) {
            return false;
          }
          cur = cur.next;
        }
        return true;
      }
    

    方法三:使用Set存储遍历过的节点

    使用Set将遍历过的节点保存下来,每次走到新的节点时先查询Set中是否存在该节点,若存在,则说明有环

     public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<>();
        ListNode cur = head;
        while (true) {
          if (cur == null) {
            return false;
          }
          if (visited.contains(cur)) {
            return true;
          }
          visited.add(cur);
          cur = cur.next;
        }
      }
    

    LeetCode24.两两交换链表中的节点

    题目链接:LeetCode24. 两两交换链表中的节点

    题目概要

    给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

    方法一:使用递归

    想到了反转链表中的递归解决,这个解法就很容易想到了
    需要注意的是,当节点个数为奇数时,最后一个是不用交换的。节点个数为偶数时,两两相邻节点会被交换。
    在这里插入图片描述

    public ListNode swapPairs1(ListNode head) {
       if (head.next == null || head == null) {
         return head;
       }
       ListNode next = swapPairs1(head.next.next);
       ListNode pre = head.next;
       head.next = next;
       pre.next = head;
       return pre;
     }
    

    如果对这段代码不是很理解,可以结合下图来辅助理解,整个过程是从右到左的。
    在这里插入图片描述

    方法二:使用指针进行迭代(从左至右)

    使用递归的解法是从右到左的顺序来进行交换。使用指针从左到右来进行交换。

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
          return head;
        }
        ListNode cur = head;
        head = head.next;
        //这是一个工具节点,用来指示当前节点的上一个节点
        ListNode last = new ListNode(-1);
        while (cur != null && cur.next != null) {
          ListNode next = cur.next.next;
          ListNode prev = cur.next;
    
          prev.next = cur;
          cur.next = next;
          last.next = prev;
          
          last = cur;
          cur = next;
        }
        return head;
      }
    

    对上面的代码不理解,可以参照下图便于理解
    在这里插入图片描述

    LeetCode142. 环形链表 II

    题目链接:LeetCode142. 环形链表 II
    题目概要

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。
    说明:不允许修改给定的链表。

    这个题目和LeetCode141. 环形链表看起来差不多。区别在于一个仅需要判断有环没环,另一个则需要返回入环的第一个节点。

    刚做这个题目时,第一时间想到了快慢指针,因此将LeetCode141. 环形链表的快慢指针的代码修改了下便进行提交,发现根本通过不了,这才想到了问题所在:快慢指针相遇的节点并不一定是入环的第一个节点

    方法一:使用Set存储遍历过的节点

    public ListNode detectCycle(ListNode head) {
       if (head == null || head.next == null) {
         return null;
       }
       Set<ListNode> visited = new HashSet<>();
       ListNode cur = head;
       while (cur != null) {
         if (visited.contains(cur)) {
           return cur;
         }
         visited.add(cur);
         cur = cur.next;
       }
       return null;
     }
    

    方法二:使用快慢指针

    快慢指针,可以在环的任一位置相遇。因此不能将快指针 = 慢指针的这个节点作为入环的第一个节点返回。
    在这里插入图片描述

    那么入环的第一个节点与快慢指针相遇的节点之间是否有关系呢?当然有!

    任意时刻,快指针走过的距离都为慢指针的 2 倍。因此,我们有:
    a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)。n代表的是快指针绕环的圈数。
    当快指针和慢指针相遇时,我们再额外使用一个指针ptr,它指向链表头部;随后,它和 慢指针每次向前移动一个位置。最终,它们会在入环点相遇。为什么呢?
    看这个等式:a=c+(n−1)(b+c)。当ptr指针从head遍历到入环的第一个节点时,ptr走过的距离为a。
    那慢指针呢?根据等式,慢指针走过的距离为c + (n−1)(b+c)。n代表的是快指针绕环的圈数,肯定会大于等于1,而且一定是个正整数。b+c刚好就是整个环的距离(也就是环的周长)。慢指针走过了c这么一段距离以后来到了入环的第一个节点,还需要走(n−1)(b+c)这么长的距离,相当于是b还要绕n - 1圈。不管是绕几圈,b最终都会回到入环的第一个节点。而此时ptr也走过了a这么长的距离来到了入环的第一个节点,两个指针便相遇了。

    详情可以查看官方题解:LeetCode官方题解

    第一次写的代码,直接根据LeetCode141. 环形链表中的快慢指针改了改。
    对比这两段代码,我仅仅新增了蓝色方框的这部分代码。
    看起来好像没什么错误,一提交就发现过不了,显示超时。为什么呢?问题出在红色方框的这部分。
    quick = head.next.next的时候,slow应该为head.next。即快指针走两步时,慢指针应该走一步。但是图中的代码却是slow = head。明显slow起跑晚了。
    在这里插入图片描述
    这会导致什么问题嗯?左边这段代码是LeetCode141. 环形链表中的,这代码能在LeetCode中通过,尽管这是一段错误的代码。
    为什么呢?

    在仅仅需要判断是否有环的时候,尽管slow指针的起步慢了。但是slow指针终究还是会进入环。一旦进入环,由于quick的移动速度是slow的两倍,相当于是在环形跑道上进行追逐,不管slow在这个环形跑道的任何位置,由于quick的速度是slow的两倍,quick一定会追上slow的。可以看一下下面这个图便于理解:

    在这里插入图片描述

    但是,如果继续保持这样的代码,在本题就不适用了。

    看下图。如果初始是slow = head,那么最终slowquick会相遇在2这个节点。这个时候,ptrslow是永远也不会相遇的,那就更别提在2这个节点相遇。

    如果初始是slow = head.next,那么最终slowquick会相遇在-4这个节点,这个时候ptrslow会在2这个节点相遇。
    在这里插入图片描述
    最终通过的代码如下:

    public boolean hasCycle(ListNode head) {
      if (head == null || head.next == null) {
        return false;
      }
      ListNode quick = head.next.next, slow = head.next;
      while (quick != slow) {
        if (quick == null || quick.next == null) {
          return false;
        }
        quick = quick.next.next;
        slow = slow.next;
      }
      return true;
    }
    

    LeetCode25. K 个一组翻转链表

    题目链接:LeetCode25. K 个一组翻转链表
    题目概要

    给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
    k 是一个正整数,它的值小于或等于链表的长度。
    如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
    示例:
    给你这个链表:1->2->3->4->5
    当 k = 2 时,应当返回: 2->1->4->3->5
    当 k = 3 时,应当返回: 3->2->1->4->5

    方法一:使用递归

    前面的链表题目用来很多递归的解法,写着写着手就顺了。
    这个题目就是LeetCode24. 两两交换链表中的节点的困难版。在两两交换链表中的节点中我们只用考虑两个节点之间的交换,而在这里面我们要考虑K个节点的交换,因此还要结合一下LeetCode206. 反转链表 中的内容。
    我们要将这K个节点看作一个整体,每次移动K个节点进行交换。根据递归,首先移动都最后的节点,如果最后的节点数不满K,就直接返回这一串链表,不需要对这些链表翻转。
    还有一种情况,就是当K=1的时候,其实也不需要进行翻转,保持原样即可。

    在递归的程序中,我是先判断从当前的head节点开始(包括head节点)是否有K个节点,如果节点数目根本不够K个,则不需要对其做任何操作,直接返回head。返回的这个节点被作为上一组节点的next节点。

    如果从当前的head结点开始计数,发现链表中节点的数目满足K个,则反转从head节点开始(包括head节点)的K个节点。反转的代码其实和LeetCode206. 反转链表中的递归代码类似。
    在这里插入图片描述

    /**
      * k个一组翻转链表,如果k==1,则不发生翻转
      * <p>
      * 给定链表:1->2->3->4->5
      * 当 k = 2 时,应当返回: 2->1->4->3->5
      * 当 k = 3 时,应当返回: 3->2->1->4->5
      *
      * @param head
      * @param k
      * @return
      */
     public ListNode reverseKGroup(ListNode head, int k) {
       //k = 1,时,不发生翻转,head == null说明是走到了末尾或者是head为null
       if (head == null || k == 1) {
         return head;
       }
       ListNode next;
       ListNode kthNodeFromHead = getKthNodeFromHead(head, k);
       if (kthNodeFromHead != null) {
         next = reverseKGroup(kthNodeFromHead.next, k);
       } else {
         return head;
       }
    
       //对当前的k个元素进行翻转,翻转以后,最后一个元素变为第一个元素,第一个元素变为最后一个元素
       ListNode last = reverseKNode(head, kthNodeFromHead);
       last.next = next;
       return kthNodeFromHead;
     }
    
     /**
      * 获得从当前的head节点开始的第K个节点,比如head -> 1 -> 2 -> 3 -> 4获得k = 3的节点,
      * 即返回值为3的这个节点
      *
      * @param head
      * @param k
      * @return 如果能得到第K个节点,则返回该节点,否则返回Null
      */
     public ListNode getKthNodeFromHead(ListNode head, int k) {
       int count = 1;
       ListNode cur = head;
       while (cur != null) {
         cur = cur.next;
         count++;
         if (count == k) {
           return cur;
         }
       }
       return null;
     }
    
     /**
      * 返回翻转以后的链表的最后一个节点,比如翻转[head -> 1 -> 2 -> 3 ]
      * 翻转以后变为[3 -> 2 -> 1],返回1这个节点
      * @param head
      * @param end
      * @return
      */
     public ListNode reverseKNode(ListNode head, ListNode end) {
       if (head == end) {
         return head;
       }
       ListNode prev = reverseKNode(head.next, end);
       prev.next = head;
       return head;
     }
    

    方法二:使用迭代

    复用了方法一的一些代码。

     public ListNode reverseKGroup(ListNode head, int k) {
       if (head == null || k == 1 || getKthNodeFromCur(head, k) == null) {
         return head;
       }
       ListNode prev = new ListNode(-1), cur = head;
       head = getKthNodeFromCur(head, k);
       while (getKthNodeFromCur(cur, k) != null) {
         ListNode kthNodeFromCur = getKthNodeFromCur(cur, k);
         //存储kthNodeFromCur的下一个节点
         ListNode next = kthNodeFromCur.next;
         //翻转以后kthNodeFromCur变为这个区间内链表的头节点,reverseKNode返回这个区间的最后一个节点
         ListNode last = reverseKNode(cur, kthNodeFromCur);
         prev.next = kthNodeFromCur;
         prev = last;
         cur = next;
       }
       prev.next = cur;
       return head;
     }
    
     public ListNode getKthNodeFromCur(ListNode head, int k) {
       int count = 1;
       ListNode cur = head;
       while (cur != null) {
         cur = cur.next;
         count++;
         if (count == k) {
           return cur;
         }
       }
       return null;
     }
    
     public ListNode reverseKNode(ListNode head, ListNode end) {
       if (head == end) {
         return head;
       }
       ListNode prev = reverseKNode(head.next, end);
       prev.next = head;
       return head;
     }
    
    展开全文
  • 给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回null。 说明:不允许修改给定的链表。 看到这道题,我们首先应该想到的是判断这个链表是否有环,如果有环,找到入口点,否则返回true。 怎么...

    原文地址:https://blog.csdn.net/baidu_40931662/article/details/84306202

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

    说明:不允许修改给定的链表。

    看到这道题,我们首先应该想到的是判断这个链表是否有环,如果有环,找到入口点,否则返回true。

    怎么判断链表是否有环呢?

    指定一个快指针和慢指针,快指针一次走两步,慢指针一次走一步。

    如果没有环,快指针一定会遇到null;

    如果有环,在经过一段时间后,快指针一定会和慢指针相遇。

     如果链表是有环的,怎么找到环的入口点呢?

    这需要推导一些公式:

    如图,这是一个环形链表,我们假设链表的起始点到环的入口点的距离为L,环的周长为R,环的入口点到快慢指针的相遇位置的距离为X(图中红色箭头标注的就是快慢指针的相遇点)。

    快指针走的距离:F = L+X+n*R

    慢指针走的距离:S = L+X

    注意:慢指针一定是走不到一圈就相遇了,因为如果在环的入口点没有相遇的话,快指针的速度是慢指针的两倍,慢指针在入口点时快指针已经进入环内,在慢指针走完一圈之前,快指针一定会追上它。最差的情况就是在入口点相遇,这是快指针走了两圈,慢指针刚好走了一圈,这个情况后面再讨论。

    因为快指针走的距离是慢指针的两倍,所以F = 2*S。

    这时:L+X+n*R = 2 * (L + X)

              L = n*R - X

    当n = 1时,也就是快指针走了一圈之后,在第二圈的时候遇见了慢指针,L = R - X

    我们可以发现,L是链表的表头到环的入口点的位置,(R - X)是相遇点到环入口点的位置。

    现在已经有办法得到环的入口点了,但是不要忘记一个特例:

    如果链表的表头就是环的入口点呢?

    我们可以发现,如果链表的表头就是入口点,使用快慢指针的时候,因为快指针是慢指针的速度的2倍,所以它们一定是慢指针走了一圈,快指针走了两圈的时候相遇,就是在环的入口点相遇。

    所有的情况都已经考虑到了,这时就可以想办法算入口点了。

    我们现在已经知道了相遇的位置,这时另外添加一个变量tmp指向头结点,tmp走一步,快指针(或者慢指针)走一步,当它们两相遇的时候,就是环的入口点。在这里也不要忘记特殊情况:如果相遇点等于头结点,那么头结点一定就是环的入口点。

    这时就可以动手写代码了:


    /**
     * Definition for singly-linked list.
     * class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode detectCycle(ListNode head) {
            if((head == null) || (head.next == null)){
                return null;
            }
            //使用快慢指针,若有环,相遇,否则无环
            ListNode fast = head;
            ListNode slow = head;
            while((fast != null) && (fast.next != null)){
                fast = fast.next.next;
                slow = slow.next;
                if(fast == slow){
                    //有环
                    //记住相遇点的指针,一个从相遇点开始,一个从头开始,相遇的地方就是环的入口点
                    ListNode tmp = head;
                    //假设链表的开始就是入口点
                    //如果链表的开始是入口点,最后一定在开始的位置相遇
                    //因为fast是slow的两倍,当fast走了一圈的时候,slow走半圈,最后在fast走两圈,slow走一圈的位置相遇
                    if(tmp == fast){
                        return fast;
                    }
                    while(true){
                        fast = fast.next;
                        tmp = tmp.next;
                        if(fast == tmp){
                           break;
                        }
                    }
                    return fast;
                }
            }
            return null;
        }
    }

    展开全文
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。   为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有...

      给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
      为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意 pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。

    说明:不允许修改给定的链表。

    示例1:
    在这里插入图片描述
    输入:head = [3,2,0,-4], pos = 1
    输出:返回索引为 1 的链表节点
    解释:链表中有一个环,其尾部连接到第二个节点。

    示例2:
    在这里插入图片描述
    输入:head = [1,2], pos = 0
    输出:返回索引为 0 的链表节点
    解释:链表中有一个环,其尾部连接到第一个节点。

    示例3:
    在这里插入图片描述
    输入:head = [1], pos = -1
    输出:返回 null
    解释:链表中没有环。

    思路:
      首先,找到快慢指针的交汇处;
      然后,运用数学中推导的公式,我们可以知道他们俩交点的位置到入环节点的距离,和链表第一个节点到入环节点的距离,是相等的。利用这一条件来循环找出入环节点。

    示意图:
    在这里插入图片描述

    public ListNode detectCycle(ListNode head) {
    // 判断链表是否带环
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
    // 返回快慢指针的交点
    // 此交点到环的入口点和链表第一个点到入口点的距离是相等的
            if (fast == slow) {
                break;
            }
        }
    // 跳出循环有两种可能,一种是不带环到末尾了
        if (fast == null || fast.next == null) {
            return null;
        }
    // 一种是找到了快慢指针的交点,
    // 设置两个引用
    // 一个从链表第一个位置开始遍历,一个从交点位置开始遍历
    // 他们会同时到达入环点,所以当他们相等时,返回相等点的引用。
        ListNode cur1 = head;
        ListNode cur2 = fast;
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
    展开全文
  • 输入两个链表,找出它们的第一个公共节点。 如下面的两个链表: 在节点 c1 开始相交。 二、双指针(暴力) 2.1 思路分析 采用双重循环,使用两指针p、q分别指向链表A和链表B,外循环遍历链表A,内循环遍历链表...
  • 题目:给定一个整数num,如何在节点有序的环形链表中插入一个节点值为num的节点,并保证这个环形链表依然有序。(假如链表是升序) 解决思路: 1.如果链表为空,则开辟一个节点,让后让他自己指向自己,然后返回该...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • 环形链表 环形链表—力扣链接 题目内容:给定一个链表,判断链表中是否有环 输入输出示例:true 1.代码实现 方法:利用HashSet的无重复性 public static boolean hasCycle2(ListNode head) { //思路二:;利用...
  • 判断是否存在环形链表并找到环形的入口
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • var detectCycle = function(head) { // if(!head)return null;... s=s.next //第一次相遇 if(f==s)break; } f=head; while(f!=s){ s=s.next; f=f.next } //第二次相遇的时候f已经走了链表入环口 return f };
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环...
  • C语言中,链表是种数据结构,相比较数组的连续存储,链表是种将内存分散(当前也可以连续)的数据节点通过指针的方式连接在一起,此外,链表不仅...1链表结构体首先定义环形链表节点的形式,即一个结构体,简...
  • 环形链表的入环节点

    2021-04-07 17:20:48
    给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • 环形链表Ⅱ(链表环的入口节点) 题目 给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。 思路 快慢指针法,声明两指针 P1 P2 1.判断链表是否有环: P1 P2 从头部出发,P1走两步,P2走...
  • 环形链表I 题目描述: 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表...解释:链表中有一个环,其尾部连接到个节点。 示例 2: 输入:head = [1,2], pos =...
  • 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • 分析:可以使用一map来记录每遍历过的节点,当遍历到一之前遍历过的节点时(第一次出现这种情况),则说明链表存在环了且这个节点是环的第一个节点,实现如下: /** * Definition for singly-linked list. *...
  • 环形链表找入口节点

    2020-08-15 15:00:33
    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。...
  • 随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。 如下图所示,设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b ...
  • Linked List Cycle II(Medium) 给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。不允许修改给定的链表。 示例: 输入: 输出:结点 <2> 解释:链表中有一环,其尾部连接到第二结点...
  • 个链表第一个公共节点 题目描述: 输入两个链表,找出它们的第一个公共结点。(注意因为传入数据是链表, 所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)。 问题分析: 有这样几种思路: ...
  • 链表倒数n个节点

    2017-03-29 23:58:28
     样例:给出链表 3->2->1->5->null和n = 2,返回倒数个节点的值1. 解题思路:创建新链表来创建两指针dummy和head,用head遍历链表得出链表的长度。  用dummy进行for循环,遍历到sum-1个节点,就得到倒数...
  • 原题链接: 环形链表II. 解题思路 、哈希表 依次遍历整个链表,并创建一个哈希表来存储遍历过的节点,当要存入的节点已经存在于哈希表中,返回该节点即可。若遍历到某节点的next节点为null,说明链表没有环,
  • 环形链表Ⅱ 解法: 使用HashSet存储每个节点: public class Solution { public ListNode detectCycle(ListNode head) { ListNode node = head; HashSet<ListNode> set = new HashSet<ListNode>()...
  • 保证环形链表从头节点开始到最后一个节点是非降序排序。 解题方法1 比如,环形链表1 2 2 3 5 5 7 当num=3,新节点应该插入到个节点个节点之间,当num=8,新节点应该在尾节点和头节点之间,当num=0...
  • 图解Java数据结构之环形链表

    千次阅读 2019-08-08 15:01:38
    单链表的最后一个结点的链域指向NULL,而环形链表的建立,不要专门的头结点,让最后一个结点的链域指向链表结点。 简单点说链表首位相连,组成环状数据结构。如下图结构: 而在环形链表中,最为著名的即是约瑟夫环...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,281
精华内容 5,712
热门标签
关键字:

环形链表的第一个节点