怎么免费做公司网站,wordpress版本不一致如何更换空间,网络营销专业,客源引流推广app160.链表相交 我的思路代码改进 LeetCode#xff1a;给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点#xff0c;返回 null 。 我的思路
计算链表A、B的长度count1、count2。临时指针curA、curB要同时指向… 160.链表相交 我的思路代码改进 LeetCode给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。 我的思路
计算链表A、B的长度count1、count2。临时指针curA、curB要同时指向距离A、B链表尾端相同的位置。因此长链表的指针往后移动count1-count2 或者 count2-count1。两个指针同时移动如果同时指向一个节点该节点就是相交节点。 Java 实现 public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode dummyheadA new ListNode(-1);dummyheadA.next headA;ListNode dummyheadB new ListNode(-2);dummyheadB.next headB;ListNode curA dummyheadA;ListNode curB dummyheadB;int count10,count20;//count1没有初始化while(curA.next!null) {count1;curA curA.next;}while(curB.next!null) {count2;curB curB.next;}curA dummyheadA;curB dummyheadB;if(count1 count2) {//A长for(int i0; i(count1-count2); i) {curA curA.next;}} else {//B长for(int i0; i(count2-count1); i) {curB curB.next;}}//AB长度一样while(curA ! null) {if(curA curB) {return curA;} else {curA curA.next;curB curB.next;}}return null;}
}代码改进
1 本题不涉及增删可以不用头节点 2 第23行到31行有更简便的实现方式。因为目的是让指向长链表的指针后移所以可以规定curA这个变量指向长节点。 从代码随想录截取的代码片段。 // 让curA为最长链表的头lenA为其长度
if (lenB lenA) {//1. swap (lenA, lenB);int tmpLen lenA;lenA lenB;lenB tmpLen;//2. swap (curA, curB);ListNode tmpNode curA;curA curB;curB tmpNode;
}
// 求长度差
int gap lenA - lenB;
// 让curA和curB在同一起点上末尾位置对齐
while (gap-- 0) {curA curA.next;
}
