外贸营销型网站设计,网站怎么申请微信认证,网站推广包含哪些方法,网站建设中最基本的决策之一是Leetcode 02.07 链表相交#xff08;链表#xff09; 解法1 尾部对齐解法2#xff1a;太厉害了#xff0c;数学归纳推导的方法 很巧妙#xff0c;这就是将链表的尾端对齐后再一起遍历#xff0c;这样能满足题目的要求。因为相交之后两个链表到结束的所有节点都一样了链表 解法1 尾部对齐解法2太厉害了数学归纳推导的方法 很巧妙这就是将链表的尾端对齐后再一起遍历这样能满足题目的要求。因为相交之后两个链表到结束的所有节点都一样了数目也一样。 解法1 尾部对齐
时间复杂度O(MN) 空间复杂度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 移动了 acb 次、指针 pB 移动了 bca次之后两个指针会同时到达两个链表相交的节点该节点也是两个指针第一次同时指向的节点此时返回相交的节点。 如果两个链表不相交也是一样的道理当PA指针和PB指针同时遍历mn后会同时指向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; }
}
