如何判断一个链表有环
方法是使用快慢指针, 通过一个 slow 指针 (每次都指向下一个), 一个 quick 指针 (每次都指向下面两个)
因为假设有环的话, quick 会追上 slow 指针
找到环出口就是通过 slow 指针指向头节点, quick 指针指向之前环的交叉点, 然后一直以不同速度遍历直到相遇
这样找到的就是出口节点
java 实现方法如下
package 测评;
- import org.junit.Test;
- public class Main5 {
- // node
- private static class node {
- int val;
- node next = null;
- public node(int a) {
- this.val = a;
- }
- }
- //
- public static node create() {
- // 创建
- node first = new node(0);
- node node = first;
- int i = 1;
- while (i <10) {
- node.next = new node(i);
- node = node.next;
- i++;
- }
- i = 0;
- node node2 = first;
- while (i < 6) {
- if (i == 5) {
- node.next = node2;
- } else {
- node2 = node2.next;
- }
- i++;
- }
- return first;
- }
- //
- @Test
- public void test_circle() {
- node first = create();
- // 快慢指针方法判断是否为环
- node quick = first;
- node slow = first;
- int i = 0;
- while (i < 1000) {
- quick = quick.next.next;
- slow = slow.next;
- if (quick == slow) {
- System.out.println("这个是一个环");
- break;
- }
- i++;
- }
- }
- //
- // 主要是通过快慢指针来判断, 慢指针从 first 节点触发, 快指针从交叉点出发, 最后的交点就是出口节点
- @Test
- public void test_getNode() {
- node first = create();
- // 快慢指针方法判断是否为环
- node jiaodian = null;
- node quick = first;
- node slow = first;
- int i = 0;
- while (i < 1000) {
- quick = quick.next.next;
- slow = slow.next;
- if (quick == slow) {
- break;
- }
- i++;
- }
- //
- slow = first;
- while(i<1000) {
- slow = slow.next;
- quick = quick.next.next;
- if(slow == quick) {
- System.out.println("出口节点"+slow.val);
- break;
- }
- }
- }
- }
第二个问题就是判断两个链表是否有交点
判断还是很简单的, 只要将两个链表遍历到尾节点, 如果尾节点相同, 这样就证明这两个链表是有交点的
如何找到两个链表相交的节点?
方法: 遍历两个链表的长度, 然后长链表长度减去短链表长度为 K, 让长链表减去 K, 然后两个链表逐个对比
Java 代码
- @Test
- public void test() {
- // 创建两个链表
- node first1 = new node(0);
- node node1 = first1;
- node first2 = new node(0);
- node node2 = first2;
- int i=0;
- while(i<5) {
- node1.next = new node(i);
- i++;
- }
- i=0;
- while(i<5) {
- node2.next = new node(i);
- i++;
- }
- node ban = new node(6);
- node node3 = ban;
- i=0;
- while(i<5) {
- node3 = new node(i+5);
- i++;
- }
- node1.next = ban;
- node2.next = ban;
- //
- // 这里是判断
- int length_1 = 0;
- int length_2 = 0;
- node1 = first1;
- node2 = first2;
- while(node1 != null) {
- length_1++;
- node1 = node1.next;
- }
- while(node2 != null) {
- length_2++;
- node2 = node2.next;
- }
- int k = 0;
- if(length_1>=length_2) {
- k = length_1-length_2;
- int j = 0;
- while(j<k) {
- first1 = first1.next;
- j++;
- }
- }else {
- k = length_2 - length_1;
- int j = 0;
- while(j<k) {
- first2 = first2.next;
- j++;
- }
- }
- while(true) {
- if(first1 == first2) {
- System.out.println("共同节点"+first1.val);
- break;
- }
- first1 = first1.next;
- first2 = first2.next;
- }
- }
来源: https://www.cnblogs.com/feizhai/p/9653264.html