JAVA实现链表面试题(2)

代码测试：

 public static void main(String[] args) {
 LinkList list1 = new LinkList();
 LinkList list2 = new LinkList();
 //向LinkList中添加数据
 for (int i = 0; i < 4; i++) {
  list1.add(i);
  }
 for (int i = 3; i < 8; i++) {
  list2.add(i);
 }
 LinkList list3 = new LinkList();
 list3.head = list3.mergeLinkList(list1.head, list2.head); //将list1和list2合并，存放到list3中
 
 list3.print(list3.head);// 从head节点开始遍历输出
 }

上方代码中用到的add方法和print方法和第1小节中是一致的。

运行效果：

注：《剑指offer》中是用递归解决的，感觉有点难理解。

6、单链表的反转：【出现频率最高】

例如链表：

1->2->3->4

反转之后：

4->2->2->1

思路：

从头到尾遍历原数组，每遍历一个结点，将其摘下放在新链表的最前端。注意链表为空和只有一个结点的状况。时间复杂度为O（n）

方法1：（遍历）

 //方法：链表的反转
 public Node reverseList(Node head) {
 //如果链表为空或者只有一个节点，无需反转，直接返回原链表的头结点
  if (head == null || head.next == null) {
  return head;
 }
 Node current = head;
 Node next = null; //定义当前结点的下一个结点
  Node reverseHead = null; //反转后新链表的表头
 
 while (current != null) {
  next = current.next; //暂时保存住当前结点的下一个结点，因为下一次要用
 
  current.next = reverseHead; //将current的下一个结点指向新链表的头结点
  reverseHead = current; 
  current = next; // 操作结束后，current节点后移
 }
 
 return reverseHead;
 }

上方代码中，核心代码是第16、17行。

方法2：（递归）

这个办法有点难，先不讲了。

7、从尾到头打印单链表：

对于这些颠倒顺序的弊端，我们需要经常想到栈，后进先出。所以，这一题要么自己使用栈，要么让平台使用栈，也就是递归。注意数组为空的状况。时间复杂度为O（n）

注：不要想着先将单链表反转，然后递归输出，这样会破坏链表的结构，不建议。

方法1：（自己新建一个栈）

 //方法：从尾到头打印单链表
 public void reversePrint(Node head) {
 
 if (head == null) {
  return;
  }
 
  Stack<Node> stack = new Stack<Node>(); //新建一个栈
  Node current = head;
 
  //将链表的所有结点压栈
  while (current != null) {-
  stack.push(current); //将当前结点压栈
  current = current.next;
 }
  //将栈中的结点打印输出即可
 while (stack.size() > 0) {
  System.out.println(stack.pop().data); //出栈操作
 }
 }

方法2：（使用平台的栈：递归，代码优雅简单）

 public void reversePrint(Node head) {
 
 
  if (head == null) {
  return;
  }
 reversePrint(head.next);
 System.out.println(head.data);
 }

总结：方法2是基于递归实现的，戴安看起来简洁时尚，但有个问题：当链表很长的之后，就会造成方法调用的层级很深，有也许导致栈溢出。而技巧1的显式用栈，是基于循环推动的，代码的鲁棒性要更好一些。

8、判断单链表是否有环：

这里只是用到两个指针，如果一个链表有环，那么用一个指针去遍历，是依然走不到头的。

因此，我们用两个指针去遍历：first指针每次走一步，second指针每次走两步，如果first指针和second指针相遇，说明有环。时间复杂度为O (n)。

方法：

 //方法：判断单链表是否有环
 public boolean hasCycle(Node head) {
 
  if (head == null) {
  return false;
  }
 
  Node first = head;
  Node second = head;
 
  while (second != null) {
  first = first.next; //first指针走一步
  second = second.next.next; second指针走两步
 
  if (first == second) { //一旦两个指针相遇，说明链表是有环的
   return true;
  }
 }
 
  return false;
 }

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

这里，我们还必须加一个重载的add(Node node)方法，在构建单向循环链表时要用到。

LinkList.java:
 public class LinkList {
 public Node head;
 public Node current;
 
 //方法：向链表中添加数据
 public void add(int data) {
  //判断链表为空的时候
  if (head == null) {//如果头结点为空，说明这个链表还没有创建，那就把新的结点赋给头结点
  head = new Node(data);
  current = head;
 } else {
  //创建新的结点，放在当前节点的后面（把新的结点合链表进行关联）
  current.next = new Node(data);
  //把链表的当前索引向后移动一位
  current = current.next;
  }
 }
 
 
 //方法重载：向链表中添加结点
 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 boolean hasCycle(Node head) {
 
  if (head == null) {
  return false;
  }
 
  Node first = head;
  Node second = head;
 
  while (second != null) {
  first = first.next; //first指针走一步
  second = second.next.next; //second指针走两步
 
  if (first == second) { //一旦两个指针相遇，说明链表是有环的
   return true;
  }
  }
 
  return false;
 }
 
 class Node {
  //注：此处的两个成员变量权限不能为private，因为private的权限是仅对本类访问。
  int data; //数据域
  Node next;//指针域
 
  public Node(int data) {
  this.data = data;
  }
 }
 
 public static void main(String[] args) {
  LinkList list = new LinkList();
  //向LinkList中添加数据
  for (int i = 0; i < 4; i++) {
  list.add(i);
  }
 
  list.add(list.head); //将头结点添加到链表当中，于是，单链表就有环了。备注：此时得到的这个环的结构，是下面的第8小节中图1的那种结构。
 
  System.out.println(list.hasCycle(list.head));
 }
 }

检测单链表是否有环的代码是第50行。

88行：我们将头节点再次往数组中添加，此时单链表就环了。最终运行效果为true。

如果删掉了88行代码，此时单链表没有环，运行效果为false。

9、取出有环链表中，环的长度：

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

上图中环的长度是4。

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

此时，上图中环的长度就是3了。

那如何求出环的长度呢？

思路：

这上面，我们应该先运用前面的第7小节中的hasCycle方法（判断链表是否有环的哪个方式），这个办法的返回值是boolean型，但是今天要把这个办法稍做更改，让其返回值为相遇的哪个节点。然后，我们拿到这个相遇的结点就好办了，这个节点必定是在环里嘛，我们可以让这个节点对应的指针仍然向下走链表结构 java代码，直到它回到原点，就可以算出环的长度了。

方法：

 //方法：判断单链表是否有环。返回的结点是相遇的那个结点
 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;
 }

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