两个链表的交叉
题意
请写一个程序，找到两个单链表最开始的交叉节点。
注意事项:
- 如果两个链表没有交叉，返回
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 位开始，从较短节点的头节点开始，依次向后，如果两个元素相同，则说明为交叉点。
代码实现
哈希表
/**
* 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;
}
}
取长度法
/**
* 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;
}
}
原题地址
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-08-292，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录