Leetcode 02.07 链表相交（链表）

本文主要是介绍Leetcode 02.07 链表相交（链表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

很巧妙，这就是将链表的尾端对齐后再一起遍历，这样能满足题目的要求。因为相交之后两个链表到结束的所有节点都一样了，数目也一样。

解法1 尾部对齐

时间复杂度O(M+N)
空间复杂度O(1)

/*** 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) {ListNode curA = headA;ListNode curB = headB;int Alen = 0, Blen = 0;if(headA == null || headB == null) return null;// 求两个链表的长度while(curA != null){curA = curA.next;Alen ++;}while(curB != null){curB = curB.next;Blen ++;}curB = headB;curA = headA;// 【长短尾部对齐】让短的那个的头结点还是其之前的头结点，长的的cur右移（长-短）if(Alen > Blen){ for(int i = 0; i < (Alen - Blen); i++){curA = curA.next;}} else if(Alen < Blen){ for(int i = 0; i < (Blen - Alen); i++){curB = curB.next;}}// 接下来curA 和 curB 一起向后移动寻找一样的节点while(curA != null){if(curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}

解法2：太厉害了，数学归纳推导的方法

在指针 pA 移动了 a+c+b 次、指针 pB 移动了 b+c+a次之后，两个指针会同时到达两个链表相交的节点，该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
如果两个链表不相交也是一样的道理，当PA指针和PB指针同时遍历m+n后，会同时指向null。

时间复杂度O(1)
空间复杂度O(1)

/*** 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) {if(headA == null || headB == null) return null;ListNode PA = headA;ListNode PB = headB;// 同时遍历PA,PB，当PA到null则再指向headB，当PB到null则再指向headA// 遇到PA = PB 则返回该值// 最后同时指向null则返回nullwhile(PA != PB){if(PA == null) {PA = headB;continue;}if(PB == null) {PB = headA;continue;}PA = PA.next;PB = PB.next;}if(PA == null) return null;else return PA; }
}    

这篇关于Leetcode 02.07 链表相交（链表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---