Intersection of Two Linked Lists(两个链表的第一个公共节点)
2024-09-05 03:42:00
来源:https://leetcode.com/problems/intersection-of-two-linked-lists
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
# begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
两个指针分别从两个头节点出发,若走完一个链表再从另一个链表的头节点继续前进,这样两个指针一定会经过同一个节点(若没有公共节点则最后都为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) {
ListNode p1 = headA, p2 = headB;
while(p1 != p2) {
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
}
最新文章
- Linux 设备驱动程序 字符设备
- 启动odoo-10.0成功,但是访问时出错
- iOS 手势操作:拖动、捏合、旋转、点按、长按、轻扫、自定义
- Simulate a seven-sided die using only five-sided
- BZOJ 1697: [Usaco2007 Feb]Cow Sorting牛排序
- [html][转]常用返回顶部代码
- POJ 1985 Cow Marathon &;&; POJ 1849 Two(树的直径)
- 几款命令行工具(CMD)增强软件
- ACM_基础知识(二)
- 最短路问题之Dijkstra算法
- Shell命令-文件及目录操作之ls、cd
- Javascript 继承和多态
- django建立管理系统之五----单页ajax数据交互
- Java 并发编程-再谈 AbstractQueuedSynchronizer 3 :基于 AbstractQueuedSynchronizer 的并发类实现
- java使用document解析xml文件
- JVM(一)—— 内存管理
- 加拿大抢先低调上架技嘉RTX 2060 显卡
- python代码实现经典排序算法
- Python爬虫学习——光学字符识别
- springmvc中Controller方法的返回值