java语言 百分网手机站

JAVA实现链表面试题讲解(2)

时间:2020-08-09 08:19:18 java语言 我要投稿

JAVA实现链表面试题讲解

  9、取出有环链表中,环的长度:

  我们平时碰到的有环链表是下面的这种:(图1)

  上图中环的长度是4。

  但有可能也是下面的这种:(图2)

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

  那怎么求出环的长度呢?

  思路:

  这里面,我们需要先利用上面的第7小节中的hasCycle方法(判断链表是否有环的那个方法),这个方法的返回值是boolean型,但是现在要把这个方法稍做修改,让其返回值为相遇的那个结点。然后,我们拿到这个相遇的结点就好办了,这个结点肯定是在环里嘛,我们可以让这个结点对应的指针一直往下走,直到它回到原点,就可以算出环的长度了。

  方法:

  //方法:判断单链表是否有环。返回的结点是相遇的那个结点

  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;

  }

  完整版代码:(包含测试部分)

  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);

  }

  }

  11、判断两个单链表相交的第一个交点:

  《编程之美》P193,5.3,面试题37就有这道题。

  面试时,很多人碰到这道题的第一反应是:在第一个链表上顺序遍历每个结点,每遍历到一个结点的时候,在第二个链表上顺序遍历每个结点。如果在第二个链表上有一个结点和第一个链表上的结点一样,说明两个链表在这个结点上重合。显然该方法的时间复杂度为O(len1 * len2)。

  方法1:采用栈的思路

  我们可以看出两个有公共结点而部分重合的链表,拓扑形状看起来像一个Y,而不可能是X型。 如下图所示:

  如上图所示,如果单链表有公共结点,那么最后一个结点(结点7)一定是一样的,而且是从中间的某一个结点(结点6)开始,后续的结点都是一样的。

  现在的问题是,在单链表中,我们只能从头结点开始顺序遍历,最后才能到达尾结点。最后到达的尾节点却要先被比较,这听起来是不是像“先进后出”?于是我们就能想到利用栈的特点来解决这个问题:分别把两个链表的结点放入两个栈中,这样两个链表的尾结点就位于两个栈的栈顶,接下来比较下一个栈顶,直到找到最后一个相同的结点。

  这种思路中,我们需要利用两个辅助栈,空间复杂度是O(len1+len2),时间复杂度是O(len1+len2)。和一开始的蛮力法相比,时间效率得到了提高,相当于是利用空间消耗换取时间效率。

  那么,有没有更好的方法呢?接下来要讲。

  方法2:判断两个链表相交的第一个结点:用到快慢指针,推荐(更优解)

  我们在上面的方法2中,之所以用到栈,是因为我们想同时遍历到达两个链表的尾结点。其实为解决这个问题我们还有一个更简单的办法:首先遍历两个链表得到它们的长度。在第二次遍历的时候,在较长的链表上走 |len1-len2| 步,接着再同时在两个链表上遍历,找到的第一个相同的结点就是它们的第一个交点。

  这种思路的时间复杂度也是O(len1+len2),但是我们不再需要辅助栈,因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候,就可以动手写代码了。

  核心代码:

  //方法:求两个单链表相交的第一个交点

  public Node getFirstCommonNode(Node head1, Node head2) {

  if (head1 == null || head == null) {

  return null;

  }

  int length1 = getLength(head1);

  int length2 = getLength(head2);

  int lengthDif = 0; //两个链表长度的差值

  Node longHead;

  Node shortHead;

  //找出较长的那个链表

  if (length1 > length2) {

  longHead = head1;

  shortHead = head2;

  lengthDif = length1 - length2;

  } else {

  longHead = head2;

  shortHead = head1;

  lengthDif = length2 - length1;

  }

  //将较长的那个链表的指针向前走length个距离

  for (int i = 0; i < lengthDif; i++) {

  longHead = longHead.next;

  }

  //将两个链表的指针同时向前移动

  while (longHead != null && shortHead != null) {

  if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点

  return longHead;

  }

  longHead = longHead.next;

  shortHead = shortHead.next;

  }

  return null;

  }

  //方法:获取单链表的长度

  public int getLength(Node head) {

  if (head == null) {

  return 0;

  }

  int length = 0;

  Node current = head;   while (current != null) {

  length++;

  current = current.next;

  }

  return length;

【JAVA实现链表面试题讲解】相关文章:

讲解Java的Spring框架中的AOP实现11-25

java讲解11-24

讲解Java的Socket网络编程的多播与广播实现11-24

java ClassLoader机制讲解11-25

链表的C语言实现方法编程学习11-24

Java原理面试题10-05

Java面试题(精选)10-05

Java线程面试题10-05

Java 问答面试题10-05

java知识点讲解11-24