链表相关算法问题

本文中的链表节点定义如下

@Data
class Node {
  private int data;
  private Node next;
  public Node(int data) {
    this.data = data;
  }
 // 省略 getter/setter 方法
}

寻找单向链表倒数第N个节点信息

1. 暴力法,通过判断剩余节点的长度判断所处的位置,通过下图可知，后续节点的个数+1 就是其倒数节点的索引位置

@Test
/* 寻找倒数第N个节点的信息 */
public void testFindIndexFromLast() {
  // 初始化一个链表，其值为0->1->2->3 .... 7 -> 8 -> 9 这里因为篇幅问题暂略
  Node preLink = init();
  // 寻找倒数第3个节点，断言其Data = 7  
  Node data = LinkUtils.findIndexFromLast(preLink, 3);
  assert Objects.equals(Objects.requireNonNull(data).getData(), 7);
}
/* 暴力法寻找倒数第N个节点 */
public static Node findIndexFromLast(Node t, int index) {
  int length = length(t);
  if (index > length) {
    throw new RuntimeException("节点数据不足");
  }
  Node tmp = t;
  while (tmp.getNext() != null) {
    if (length(tmp) == index - 1) {
      return tmp;
    }
    tmp = tmp.getNext();
  }
  return null;
}

1. 双指针法

通过定义两个指针的方式，假设总链表长度为S，需要查询倒数第L节点的信息，那么A指针指向头结点，B指针指向第L个节点，然后A指针和B指针一直向后移动，直到B指针指向尾结点，那么B指针总共走了S-A步，同样A指针则走了S-L步，也就是说当B节点指向尾结点的时候，A的Next节点就是倒数第L个节点。

@Test
/* 寻找倒数第N个节点的信息 */
public void testFindIndexFromLast() {
  // 初始化一个链表，其值为0->1->2->3 .... 7 -> 8 -> 9 这里因为篇幅问题暂略
  Node preLink = init();
  // 寻找倒数第3个节点，断言其Data = 7  
  Node data = LinkUtils.findIndexFromLast(preLink, 3);
  assert Objects.equals(Objects.requireNonNull(data).getData(), 7);
}
public static Node findIndexFromLatestWithDoublePoint(Node t, int index) {
  int length = length(t);
  if (index > length) {
    throw new RuntimeException("");
  }
  Node pointNode1 = t;
  Node pointNode2 = t;
  while (index > 0) {
    index--;
    pointNode1 = pointNode1.getNext();
  }
  while (pointNode1.getNext() != null) {
    pointNode1 = pointNode1.getNext();
    pointNode2 = pointNode2.getNext();
  }
  return pointNode2.getNext();
}

判断链表内是够有环

1. Floyd环判定算法 又称之为龟兔算法，通过设定不同的移动速度来分别移动两个指针，当两个指针再次相遇的时候，则说明存在环状链表，否则则不存在。

   public static boolean hasRingLinked(Node t) {
   if (t == null || t.getNext() == null) {
    return false;
   }
   Node fPoint = t, lPoint = t;
   while (fPoint.getNext() != null && fPoint.getNext().getNext() != null) {
    fPoint = fPoint.getNext().getNext();
    lPoint = lPoint.getNext();
    if (fPoint == lPoint) {
      return true;
    }
   }
   return false;
   }

获取环状链表中环的长度

这其实是两个问题，分别是判断是否有环，但有环的时候，固定快节点，让慢节点一步一步走，每走一步直接加一，直到和快节点再次相遇。

public static int getRingLength(Node t) {
  Node fPoint = t, lPoint = t;
  while (fPoint.getNext() != null && fPoint.getNext().getNext() != null) {
    fPoint = fPoint.getNext().getNext();
    lPoint = lPoint.getNext();
    if (fPoint == lPoint) {
      // 如果是环状链表，则移动慢节点直到和快节点再次相遇
      int ringLength = 1;
      lPoint = lPoint.getNext();
      while (lPoint != fPoint) {
        ringLength++;
        lPoint = lPoint.getNext();
      }
      return ringLength;
    }
  }
  return 0;
}