服务器之家

服务器之家 > 正文

JAVA实现链表面试题

时间：2020-01-04 17:01     来源/作者：生命壹号

这份笔记整理了整整一个星期，每一行代码都是自己默写完成，并测试运行成功，同时也回顾了一下《剑指offer》这本书中和链表有关的讲解，希望对笔试和面试有所帮助。

本文包含链表的以下内容：

　　1、单链表的创建和遍历

　　2、求单链表中节点的个数

　　3、查找单链表中的倒数第k个结点（剑指offer，题15）

　　4、查找单链表中的中间结点

　　5、合并两个有序的单链表，合并之后的链表依然有序【出现频率高】（剑指offer，题17）

　　6、单链表的反转【出现频率最高】（剑指offer，题16）

　　7、从尾到头打印单链表（剑指offer，题5）

　　8、判断单链表是否有环

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

　　10、单链表中，取出环的起始点（剑指offer，题56）。本题需利用上面的第8题和第9题。

　　11、判断两个单链表相交的第一个交点（剑指offer，题37）

1、单链表的创建和遍历：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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; //此步操作完成之后，current结点指向新添加的那个结点
 }
}
 
//方法：遍历链表（打印输出链表。方法的参数表示从节点node开始进行遍历
public void print(Node node) {
 if (node == null) {
 return;
 }
 
current = node;
 while (current != null) {
 System.out.println(current.data);
 current = current.next;
 }
}
 
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 < 10; i++) {
 list.add(i);
 }
 
 list.print(list.head);// 从head节点开始遍历输出
}
 
}

 

上方代码中，这里面的Node节点采用的是内部类来表示（33行）。使用内部类的最大好处是可以和外部类进行私有操作的互相访问。

注：内部类访问的特点是：内部类可以直接访问外部类的成员，包括私有；外部类要访问内部类的成员，必须先创建对象。

为了方便添加和遍历的操作，在LinkList类中添加一个成员变量current，用来表示当前节点的索引（03行）。

这里面的遍历链表的方法（20行）中，参数node表示从node节点开始遍历，不一定要从head节点遍历。

 

2、求单链表中节点的个数：

注意检查链表是否为空。时间复杂度为O（n）。这个比较简单。

核心代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//方法：获取单链表的长度
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;
}

 

3、查找单链表中的倒数第k个结点：

3.1  普通思路：

先将整个链表从头到尾遍历一次，计算出链表的长度size，得到链表的长度之后，就好办了，直接输出第(size-k)个节点就可以了（注意链表为空，k为0，k为1，k大于链表中节点个数时的情况

）。时间复杂度为O（n），大概思路如下：

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findLastNode(int index) { //index代表的是倒数第index的那个结点
 
 //第一次遍历，得到链表的长度size
 if (head == null) {
 return -1;
 }
 
 current = head;
 while (current != null) {
 size++;
 current = current.next;
}
 
 //第二次遍历，输出倒数第index个结点的数据
 current = head;
 for (int i = 0; i < size - index; i++) {
 current = current.next;
 }
 
return current.data;
}

如果面试官不允许你遍历链表的长度，该怎么做呢？接下来就是。

 3.2  改进思路：（这种思路在其他题目中也有应用）

     这里需要声明两个指针：即两个结点型的变量first和second，首先让first和second都指向第一个结点，然后让second结点往后挪k-1个位置，此时first和second就间隔了k-1个位置，然后整体向后移动这两个节点，直到second节点走到最后一个结点的时候，此时first节点所指向的位置就是倒数第k个节点的位置。时间复杂度为O（n）

代码实现：（初版）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public Node findLastNode(Node head, int index) {
 
 if (node == null) {
 return null;
 }
 
 Node first = head;
 Node second = head;
 
 //让second结点往后挪index个位置
 for (int i = 0; i < index; i++) {
 second = second.next;
 }
 
 //让first和second结点整体向后移动，直到second结点为Null
while (second != null) {
 first = first.next;
 second = second.next;
 }
 
 //当second结点为空的时候，此时first指向的结点就是我们要找的结点
return first;
}

 

代码实现：（最终版）（考虑k大于链表中结点个数时的情况时，抛出异常）

上面的代码中，看似已经实现了功能，其实还不够健壮:

　　要注意k等于0的情况；

　　如果k大于链表中节点个数时，就会报空指针异常，所以这里需要做一下判断。

核心代码如下：

   

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public Node findLastNode(Node head, int k) {
if (k == 0 || head == null) {
 return null;
 }
 
 Node first = head;
 Node second = head;
 
//让second结点往后挪k-1个位置
 for (int i = 0; i < k - 1; i++) {
 System.out.println("i的值是" + i);
 second = second.next;
 if (second == null) { //说明k的值已经大于链表的长度了
 //throw new NullPointerException("链表的长度小于" + k); //我们自己抛出异常，给用户以提示
  return null;
 }
}
 
 //让first和second结点整体向后移动，直到second走到最后一个结点
 while (second.next != null) {
 first = first.next;
 second = second.next;
 }
 //当second结点走到最后一个节点的时候，此时first指向的结点就是我们要找的结点
return first;
}

 

4、查找单链表中的中间结点：

同样，面试官不允许你算出链表的长度，该怎么做呢？

思路：

    和上面的第2节一样，也是设置两个指针first和second，只不过这里是，两个指针同时向前走，second指针每次走两步，first指针每次走一步，直到second指针走到最后一个结点时，此时first指针所指的结点就是中间结点。注意链表为空，链表结点个数为1和2的情况。时间复杂度为O（n）。

代码实现：

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//方法：查找链表的中间结点
public Node findMidNode(Node head) {
 
if (head == null) {
 return null;
}
 
Node first = head;
 Node second = head;
//每次移动时，让second结点移动两位，first结点移动一位
while (second != null && second.next != null) {
 first = first.next;
 second = second.next.next;
}
 
//直到second结点移动到null时，此时first指针指向的位置就是中间结点的位置
 return first;
}

上方代码中，当n为偶数时，得到的中间结点是第n/2 + 1个结点。比如链表有6个节点时，得到的是第4个节点。

 

5、合并两个有序的单链表，合并之后的链表依然有序：

    这道题经常被各公司考察。

例如：

链表1：

　　1->2->3->4

链表2：

　　2->3->4->5

合并后：

　　1->2->2->3->3->4->4->5

解题思路：

　　挨着比较链表1和链表2。

　　这个类似于归并排序。尤其要注意两个链表都为空、和其中一个为空的情况。只需要O (1) 的空间。时间复杂度为O (max(len1,len2))

代码实现：

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//两个参数代表的是两个链表的头结点
public Node mergeLinkList(Node head1, Node head2) {
 
if (head1 == null && head2 == null) { //如果两个链表都为空
 return null;
}
 if (head1 == null) {
 return head2;
}
 if (head2 == null) {
 return head1;
}
 
Node head; //新链表的头结点
 Node current; //current结点指向新链表
// 一开始，我们让current结点指向head1和head2中较小的数据，得到head结点
 if (head1.data < head2.data) {
 head = head1;
 current = head1;
 head1 = head1.next;
 } else {
 head = head2;
 current = head2;
 head2 = head2.next;
}
 
 while (head1 != null && head2 != null) {
 if (head1.data < head2.data) {
  current.next = head1; //新链表中，current指针的下一个结点对应较小的那个数据
  current = current.next; //current指针下移
  head1 = head1.next;
 } else {
 current.next = head2;
  current = current.next;
  head2 = head2.next;
 }
 }
 
 //合并剩余的元素
 if (head1 != null) { //说明链表2遍历完了，是空的
 current.next = head1;
 }
 
if (head2 != null) { //说明链表1遍历完了，是空的
 current.next = head2;
}
 
 return head;
}

 

代码测试：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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小节中是一致的。

运行效果：

JAVA实现链表面试题

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

 

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

例如链表：

　　1->2->3->4

反转之后：

　　4->2->2->1

思路：

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

方法1：（遍历）

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//方法：链表的反转
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：（自己新建一个栈）

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//方法：从尾到头打印单链表
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：（使用系统的栈：递归，代码优雅简洁）

   

?
1
2
3
4
5
6
7
8
9
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)。

方法：

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//方法：判断单链表是否有环
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)方法，在创建单向循环链表时要用到。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
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）

JAVA实现链表面试题

上图中环的长度是4。

但有可能也是下面的这种：（图2）

JAVA实现链表面试题

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

那怎么求出环的长度呢？

思路：

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

方法：

  

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//方法：判断单链表是否有环。返回的结点是相遇的那个结点
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;
}

 

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

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
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));
 }
 
 }

 运行效果：

JAVA实现链表面试题

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
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));
}

 

运行结果：

JAVA实现链表面试题

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

 

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

我们平时碰到的有环链表是下面的这种：（图1）

JAVA实现链表面试题

上图中环的起始点1。

但有可能也是下面的这种：（图2）

JAVA实现链表面试题

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

方法1：

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

注：为了找到环的起始点，我们需要先获取环的长度，而为了获取环的长度，我们需要先判断是否有环。所以这里面其实是用到了三个方法。

代码实现：

方法1的核心代码：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//方法：获取环的起始点。参数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;
 }

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

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
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型。 如下图所示：  

JAVA实现链表面试题

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

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

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

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

 

方法2：判断两个链表相交的第一个结点：用到快慢指针，推荐（更优解）

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

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

核心代码：
 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//方法：求两个单链表相交的第一个交点
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 链表 面试题 

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思？女生说13579是什么意思？
男生常说24816是什么意思？女生说13579是什么意思？ 2019-09-17
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
配置IIS网站web服务器的安全策略配置解决方案
配置IIS网站web服务器的安全策略配置解决方案 2019-05-23
Nginx服务器究竟是怎么执行PHP项目
Nginx服务器究竟是怎么执行PHP项目 2019-05-24
返回顶部