
文章链接
数据结构-链表-单向链表
面5笔5判断两个链表的相交结点
因为两个链表的长度不同,所以我们先获取两个链表的长度,让长链表的引用先走其插值的长度。
随后,让两个引用同时走,若两个引用相等了,那么说明此时该引用所指向的节点即为相交结点。
代码如下:
public static <T> SingleLinkedList<T>.Node<T> commonNode2(SingleLinkedList<T> list1,
SingleLinkedList<T> list2){
if(list1.head == null||list2.head == null) return null;
//计算两个链表的差值
int length1 = getlength(list1.head);
int length2 = getlength(list2.head);
int lengthDif = Math.abs(length1-length2);
SingleLinkedList<T>.Node<T> longHead =list1.head;
SingleLinkedList<T>.Node<T> shortHead =list2.head;
//长链表先走其差值
if(length1<length2){
longHead = list1.head;
shortHead = list2.head;
}
for(int i=0;i<lengthDif;i++){
longHead = longHead.next;
}
//长链表和短链表开始同时走,当两个引用的相等的时候,此时该引用所指向的节点就是相交结点
while (shortHead!=longHead){
longHead = longHead.next;
shortHead = shortHead.next;
}
return longHead;
}