JAVA实现链表面试题(3)

完整版代码：（包含测试部分）

public class LinkList {
 public Node head;
 public Node current;
 
 public int size;
 
 //方法：向链表中添加数据
 public void add(int data) {
  //判断链表为空的时候
  if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
  head = new Node(data);
  current = head;
  } else {
  //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
  current.next = new Node(data);
  //把链表的当前索引向后移动一位
  current = current.next; //此步操作完成之后，current结点指向新添加的那个结点
  }
 }
 
 
 //方法重载：向链表中添加结点
 public void add(Node node) {
  if (node == null) {
  return;
  }
  if (head == null) {
  head = node;
  current = head;
  } else {
  current.next = node;
  current = current.next;
  }
 }
 
 
 //方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
 public void print(Node node) {
  if (node == null) {
  return;
  }
 
  current = node;
  while (current != null) {
  System.out.println(current.data);
  current = current.next;
  }
 }
 
 //方法：判断单链表是否有环。返回的结点是相遇的那个结点
 public Node hasCycle(Node head) {
 
  if (head == null) {
  return null;
  }
 
  Node first = head;
  Node second = head;
 
  while (second != null) {
  first = first.next;
  second = second.next.next;
 
  if (first == second) { //一旦两个指针相遇，说明链表是有环的
   return first; //将相遇的那个结点进行返回
  }
  }
 
  return null;
 }
 
 //方法：有环链表中，获取环的长度。参数node代表的是相遇的那个结点
 public int getCycleLength(Node node) {
 
  if (head == null) {
  return 0;
  }
 
  Node current = node;
  int length = 0;
 
  while (current != null) {
  current = current.next;
  length++;
  if (current == node) { //当current结点走到原点的时候
   return length;
  }
  }
 
  return length;
 }
 
 class Node {
  //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
  int data; //数据域
  Node next;//指针域
 
  public Node(int data) {
  this.data = data;
  }
 }
 
 
 public static void main(String[] args) {
  LinkList list1 = new LinkList();
 
  Node second = null; //把第二个结点记下来
 
  //向LinkList中添加数据
  for (int i = 0; i < 4; i++) {
  list1.add(i);
  if (i == 1) {
   second = list1.current; //把第二个结点记下来
  }
  }
 
  list1.add(second); //将尾结点指向链表的第二个结点，于是单链表就有环了，备注：此时得到的环的结构，是本节中图2的那种结构
  Node current = list1.hasCycle(list1.head); //获取相遇的那个结点
 
  System.out.println("环的长度为" + list1.getCycleLength(current));
 }
 
 }

运行效果：

如果将下面的104至122行的测试代码改成以下这种的：（即：将图2中的结构改成图1中的结构）

 public static void main(String[] args) {
   LinkList list1 = new LinkList();
   //向LinkList中添加数据
   for (int i = 0; i < 4; i++) {
    list1.add(i);
   }
 
   list1.add(list1.head); //将头结点添加到链表当中（将尾结点指向头结点），于是，单链表就有环了。备注：此时得到的这个环的结构，是本节中图1的那种结构。
 
   Node current = list1.hasCycle(list1.head);
   System.out.println("环的长度为" + list1.getCycleLength(current)); 
 }

运行结果：

如果把里面的代码中的第8行删掉，那么这个数组就没有环了，于是运行的结果为0。

10、单链表中，取出环的起始点：

我们经常遇到的有环链表是上面的这些：（图1）

上图中环的起始点1。

但有也许只是上面的这些：（图2）

此时，上图中环的起始点是2。

方法1：

这里我们应该运用到后面第8小节的取出环的长度的方式getCycleLength，用这个办法来获取环的厚度length。拿到环的宽度length之后，需要用到两个指针变量first和second，先让second指针走length步；然后让first指针和second指针同时各走一步，当两个指针相遇时，相遇时的节点就是环的起始点。

注：为了找到环的起始点，我们应该先获取环的长度，而为了获得环的长度，我们必须先判定是否有环。所以这上面虽然是用到了三个方法。

代码实现：

方法1的核心代码：

 //方法：获取环的起始点。参数length表示环的长度
 public Node getCycleStart(Node head, int cycleLength) {
  if (head == null) {
    return null;
  }
 
   Node first = head;
   Node second = head;
   //先让second指针走length步
  for (int i = 0; i < cycleLength; i++) {
    second = second.next;
   }
 
   //然后让first指针和second指针同时各走一步
   while (first != null && second != null) {
    first = first.next;
    second = second.next;
   if (first == second) { //如果两个指针相遇了，说明这个结点就是环的起始点
     return first;
    }
   }
 
   return null;
  }

完整版代码：（含测试部分）

 public class LinkList {
  public Node head;
  public Node current;
 
  public int size;
 
  //方法：向链表中添加数据
  public void add(int data) {
   //判断链表为空的时候
   if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
    head = new Node(data);
    current = head;
   } else {
    //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
    current.next = new Node(data);
    //把链表的当前索引向后移动一位
    current = current.next; //此步操作完成之后，current结点指向新添加的那个结点
   }
  }
 
 
  //方法重载：向链表中添加结点
  public void add(Node node) {
   if (node == null) {
    return;
   }
   if (head == null) {
    head = node;
    current = head;
   } else {
    current.next = node;
    current = current.next;
   }
  }
 
 
  //方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
  public void print(Node node) {
   if (node == null) {
    return;
   }
 
   current = node;
   while (current != null) {
    System.out.println(current.data);
    current = current.next;
   }
  }
 
 
  //方法：判断单链表是否有环。返回的结点是相遇的那个结点
  public Node hasCycle(Node head) {
 
   if (head == null) {
    return null;
   }
 
   Node first = head;
   Node second = head;
 
   while (second != null) {
    first = first.next;
    second = second.next.next;
 
    if (first == second) { //一旦两个指针相遇，说明链表是有环的
     return first; //将相遇的那个结点进行返回
    }
   }
 
   return null;
  }
  //方法：有环链表中，获取环的长度。参数node代表的是相遇的那个结点
  public int getCycleLength(Node node) {
 
   if (head == null) {
    return 0;
   }
 
   Node current = node;
   int length = 0;
 
   while (current != null) {
    current = current.next;
    length++;
    if (current == node) { //当current结点走到原点的时候
     return length;
    }
   }
 
   return length;
  }
 
  //方法：获取环的起始点。参数length表示环的长度
  public Node getCycleStart(Node head, int cycleLength) {
 
   if (head == null) {
    return null;
   }
 
   Node first = head;
   Node second = head;
   //先让second指针走length步
   for (int i = 0; i < cycleLength; i++) {
    second = second.next;
   }
 
   //然后让first指针和second指针同时各走一步
   while (first != null && second != null) {
    first = first.next;
    second = second.next;
 
    if (first == second) { //如果两个指针相遇了，说明这个结点就是环的起始点
     return first;
   }
  }
 
   return null;
  } 
  class Node {
  //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
   int data; //数据域
   Node next;//指针域
 
   public Node(int data) {
    this.data = data;
   }
  }
 
 
  public static void main(String[] args) {
   LinkList list1 = new LinkList();
 
   Node second = null; //把第二个结点记下来
 
   //向LinkList中添加数据
   for (int i = 0; i < 4; i++) {
    list1.add(i);
 
   if (i == 1) {
    second = list1.current; //把第二个结点记下来
   }
  }
   list1.add(second); //将尾结点指向链表的第二个结点，于是单链表就有环了，备注：此时得到的环的结构，是本节中图2的那种结构
   Node current = list1.hasCycle(list1.head); //获取相遇的那个结点
 
  int length = list1.getCycleLength(current); //获取环的长度
  System.out.println("环的起始点是" + list1.getCycleStart(list1.head, length).data);
  }
 
 }

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-122053-3.html