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.
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; ListNode a = headA, b = headB; int m = 0; while(a != null) { m++; a = a.next; } int n=0; while(b != null) { n++; b = b.next; } a = headA; b = headB; while(m>n) { m--; a = a.next; } while(n>m) { n--; b = b.next; } while(a != null) { if(a == b) return a; a = a.next; b = b.next; } return null; }
重构了一下代码:
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int lenA = length(headA), lenB = length(headB); if(lenA > lenB) return getIntersectionNode(headA, lenA, headB, lenB); return getIntersectionNode(headB, lenB, headA, lenA); } private int length(ListNode head) { int len = 0; while(head != null) { len++; head = head.next; } return len; } private ListNode getIntersectionNode(ListNode a, int m, ListNode b, int n) { for(int i=0; i<m-n; i++) a = a.next; while(a != null && b != null) { if(a == b) return a; a = a.next; b = b.next; } return null; }
相关推荐
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode 接口 该项目可帮助您使用首选的 IDE 或带有命令行界面 (CLI) 的编辑器来执行 leetcode。 入门 ...leetcode ...leetcode ...two-sum leetcode ...median-of-two-sorted-arrays 然后问题描述和启动代码将自动
文件中包含了LeetCode中Tag为LinkedList的题目参考代码。
LeetCode题解 - Java语言实现-181页.pdf
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
500195422331430LeetCode题解 - Java语言实现.zip
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
leetcode-训练 算法训练。 java $: javac hello.java java $: java hello c $: gcc hello.c 如果没有错误会生成a.out 可执行文件 c $: ./a.out leetcode cli leetcode version leetcode help leetcode help user ...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我
leetcode-cli 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的网站! ⦙⦙⦙⦙⦙⦙⦙⦙ 一个很打问题的方法。 问题来缓解离线思考。 编码前的源代码。 居住和与 leetcode.com。 下载你...