校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > java语言 > 数组和链表
题目

编写一个程序,找到两个单链表相交的起始节点。
例如,下面的两个链表:

A:          a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3


解答

在节点 c1 开始相交。
注意:
1.如果两个链表没有交点,返回 null.
2.在返回结果后,两个链表仍须保持原有的结构。
3.可假定整个链表结构中没有循环。
4.程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

/**
* 返回相交单向链表的交点
*/
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}

//记录链表的长度
int lenA = 1;
ListNode tempA = headA;
while (tempA.next != null) {
lenA++;
tempA = tempA.next;
}

int lenB = 1;
ListNode tempB = headB;
while (tempB.next != null) {
lenB++;
tempB = tempB.next;
}

//判断链表是否相交,不想交直接返回null
if (!tempA.equals(tempB)) {
return null;
}

//截取后半段,相同长度的链表
int reduseCount = lenA - lenB;

tempA = headA;
tempB = headB;
if (reduseCount > 0) {
for (int i = 0; i < reduseCount; i++) {
tempA = tempA.next;
}
} else {
reduseCount = Math.abs(reduseCount);
for (int i = 0; i < reduseCount; i++) {
tempB = tempB.next;
}
}

//循环遍历找到交点
while (tempB != null && tempA != null) {
if (tempB.equals(tempA)) {
return tempB;
}
tempA = tempA.next;
tempB = tempB.next;
}

return null;
}


C 0条回复 评论

帖子还没人回复快来抢沙发