这是一道真的非常巧妙的题,题解思路如下:
如果让他们尾端队齐,那么从后面遍历就会很快找到第一个相交的点。但是逆序很麻烦。
于是有一个巧妙的思路诞生了,如果让短的先走完自己的再走长的,长的走完走短的,他俩就会正好对齐。
于是:
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode GetIntersectionNode(ListNode headA, ListNode headB) { ListNode l1 = headA, l2 = headB; while(l1 != l2) { l1 = l1.next; l2 = l2.next; //无相交 if (l1 == null && l2 == null) break; //不等长交换 if (l1 == null) l1 = headB; if (l2 == null) l2 = headA; } return l1; } }