建设铝合金窗网站,网店推广的常用方法有哪些,微信公众号和小程序区别,辽阳制作网站1.找出两个链表的交点
160. Intersection of Two Linked Lists (Easy)
Leetcode / 力扣
例如以下示例中 A 和 B 两个链表相交于 c1#xff1a;
A: a1 → a2↘c1 → c2 → c3↗
B: b1 → b2 → b3
但是不会出现以下相交的情况#xff0c;因为每个节点只有一个…1.找出两个链表的交点
160. Intersection of Two Linked Lists (Easy)
Leetcode / 力扣
例如以下示例中 A 和 B 两个链表相交于 c1
A: a1 → a2↘c1 → c2 → c3↗
B: b1 → b2 → b3
但是不会出现以下相交的情况因为每个节点只有一个 next 指针也就只能有一个后继节点而以下示例中节点 c 有两个后继节点。
A: a1 → a2 d1 → d2↘ ↗c↗ ↘
B: b1 → b2 → b3 e1 → e2
要求时间复杂度为 O(N)空间复杂度为 O(1)。如果不存在交点则返回 null。
设 A 的长度为 a cB 的长度为 b c其中 c 为尾部公共部分长度可知 a c b b c a。
当访问 A 链表的指针访问到链表尾部时令它从链表 B 的头部开始访问链表 B同样地当访问 B 链表的指针访问到链表尾部时令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
如果不存在交点那么 a b b a以下实现代码中pa和pb会同时为 null从而退出循环。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa headA, pb headB;while(pa ! pb){pa (pa null ? headB : pa.next);pb (pb null ? headA : pb.next);}return pa;}
}
2.翻转链表
206. Reverse Linked List (Easy)
Leetcode / 力扣
双指针迭代 我们可以申请两个指针第一个指针叫 pre最初是指向 null 的。 第二个指针 cur 指向 head然后不断遍历 cur。 每次迭代到 cur都将 cur 的 next 指向 pre然后 pre 和 cur 前进一位。 都迭代完了(cur 变成 null 了)pre 就是最后一个节点了。 class Solution {public ListNode reverseList(ListNode head) {ListNode pre null, cur head;while(cur ! null){ListNode tmp cur.next;cur.next pre;pre cur;cur tmp;}return pre;}
}
