两个链表的交叉

题意

请写一个程序,找到两个单链表最开始的交叉节点。

注意事项:

  • 如果两个链表没有交叉,返回 null
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。

样例

下列两个链表:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始交叉。

思路

本题不用考虑 有环链表的情况,所以较为简单。

哈希表

利用哈希表,先将 A 链表所有元素加入到哈希表中,然后遍历 B 数组,判断每一个元素是否已在哈希表中存在,如果已存在,则已存在的节点就是交叉节点。

取长度法

首先将两个链表都遍历一次,取到两个的长度,记作 m 和 n,如果两个链表有交叉,那么两个链表的最后一个节点,一定是一样的。

这里用样例中的两个链表举例, A 链表的的长度:n = 5, B 链表的长度:m = 6 ,如果两者有相交节点,那么最多也只能是从长度较少节点的头结点到未节点。所以从较长链表 B 的第 m - n 位开始,从较短节点的头节点开始,依次向后,如果两个元素相同,则说明为交叉点。

代码实现

哈希表

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/


public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;

HashSet<ListNode> map = new HashSet<ListNode>();
while (p1 != null) {
map.add(p1);
p1 = p1.next;
}

while (p2 != null) {
if (map.contains(p2)) {
return p2;
}
p2 = p2.next;
}

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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/


public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = getLength(headA);
int lenB = getLength(headB);

ListNode n1 = headA;
ListNode n2 = headB;
for (int i = 0; i < Math.abs(lenA - lenB); i++) {
if (lenA > lenB)
n1 = n1.next;
else n2 = n2.next;
}

while (n1 != null && n2 != null) {
if (n1.val == n2.val && n1.next == n2.next) {
return n1;
}
n1 = n1.next;
n2 = n2.next;
}
return null;
}

public int getLength(ListNode head) {
if (head == null) {
return 0;
}
int length = 0;
ListNode p = head;
while (p != null) {
p = p.next;
length++;
}
return length;
}
}

原题地址

LintCode:两个链表的交叉

坚持原创技术分享,您的支持将鼓励我继续创作!