LeetCode hoot100-22

160. 相交链表给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

这道题几分钟就写出来了。应该是几年前做过，这种思想还能一直记得。所以算法题是不会白做的。

我的做法
两个链表如果一个长一个短的话，就让长的那个先往后走【长链表长度和短链表长度的差】。这样两个链表再同步往后走，如果右相交的节点的话，就会同时到达那个节点。注意不要改变链表的头结点不能变，所以要重新定义一个指向头结点的节点来做链表的遍历。

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int lenA = length(headA);int lenB = length(headB);int cha = Math.abs(lenA - lenB);ListNode aa = headA;ListNode bb = headB;if (lenA > lenB) {while (cha > 0) {aa = aa.next;cha--;}} else {while (cha > 0) {bb = bb.next;cha--;}}while (aa != bb && aa != null) {aa = aa.next;bb = bb.next;}return aa;}public int length(ListNode listNode){int size = 0;while (listNode!=null){listNode = listNode.next;size ++ ;}return size;}
}

官方解法2
优雅啊。主要思想是长短两个链表都先遍历自己，完了之后去遍历对方链表。如果能有相交节点就能同时到达。A链表长m=a+c(c是A，B链表重合部分)，B链表长n=b+c(c是A，B链表重合部分)。A把自己遍历完了就是a+c,然后去遍历B链表的b那一段。整体就是走了a+c+b。同理，B把自己遍历完了就是b+c，然后去遍历A链表a那段。整体就是走了b+c+a。这个时候两个链表走的长度是相同的，如果重合就会直接相遇。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。