给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
如果A、B链表长度一样的,设置两个链表pl、ps(长的那一个和短的那一个),那我们让他们同时走,当ps与pl相遇(ps == pl)返回对应节点即可。
若A、B链表两个长度不一样,一长一短,我们可以取两个列表长度的差值(len),让长的那个列表往下走len次,(这样短的和长的就能相遇),再和短的一起走直到相遇。
具体步骤:
1.判断哪个链表更长:
设置两个链表,pl(长链表),ps(短链表),分别存放headA和headB,
1.1遍历获取两个链表的长度lenA、lenB:while循环,循环后pl与ps均为null,所以要重新赋值为headA和headB。
1.2.求两个链表长度的差值,若lenA-lenB<0,说明headB更长,将pl = headB,ps = headA.
2.让长的那个链表先走len步:
通过while循环让pl先走len步
3.pl与ps同时走直到相遇:
while循环让两个一直遍历下去。
具体代码如下:
//.判断两个链表哪个更长ListNode pl = headA;ListNode ps = headB;int LenB = 0;int lenA = 0;int len = 0;while(pl!=null){lenA++; pl = pl.next;}while(ps!=null){LenB++;ps = ps.next;}pl = headA;ps = headB;//求差值len = lenA-LenB;if(len<0){pl = headB;ps = headA;len = LenB-lenA;}//3.让最长的链表先走len步while(len!=0){pl= pl.next;len--;}//4.两个同时走,直到相遇while(pl!=ps){pl = pl.next;ps = ps.next;}if(pl == null){return null;}return pl;
}