C++实现LeetCode(160.求两个链表的交点)
[LeetCode] 160.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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
我还以为以后在不能免费做OJ的题了呢，想不到 OJ 又放出了不需要买书就能做的题，业界良心啊，哈哈^_^。这道求两个链表的交点题要求执行时间为 O(n)，则不能利用类似冒泡法原理去暴力查找相同点，事实证明如果链表很长的话，那样的方法效率很低。我也想到会不会是像之前删除重复元素的题一样需要用两个指针来遍历，可是想了好久也没想出来怎么弄。无奈上网搜大神们的解法，发觉其实解法很简单，因为如果两个链长度相同的话，那么对应的一个个比下去就能找到，所以只需要把长链表变短即可。具体算法为：分别遍历两个链表，得到分别对应的长度。然后求长度的差值，把较长的那个链表向后移动这个差值的个数，然后一一比较即可。代码如下：
C++ 解法一：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
int lenA = getLength(headA), lenB = getLength(headB);
if (lenA < lenB) {
for (int i = 0; i < lenB - lenA; ++i) headB = headB->next;
} else {
for (int i = 0; i < lenA - lenB; ++i) headA = headA->next;
}
while (headA && headB && headA != headB) {
headA = headA->next;
headB = headB->next;
}
return (headA && headB) ? headA : NULL;
}
int getLength(ListNode* head) {
int cnt = 0;
while (head) {
++cnt;
head = head->next;
}
return cnt;
}
};
Java 解法一：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
int lenA = getLength(headA), lenB = getLength(headB);
if (lenA > lenB) {
for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
} else {
for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
}
while (headA != null && headB != null && headA != headB) {
headA = headA.next;
headB = headB.next;
}
return (headA != null && headB != null) ? headA : null;
}
public int getLength(ListNode head) {
int cnt = 0;
while (head != null) {
++cnt;
head = head.next;
}
return cnt;
}
}
这道题还有一种特别巧妙的方法，虽然题目中强调了链表中不存在环，但是我们可以用环的思想来做，我们让两条链表分别从各自的开头开始往后遍历，当其中一条遍历到末尾时，我们跳到另一个条链表的开头继续遍历。两个指针最终会相等，而且只有两种情况，一种情况是在交点处相遇，另一种情况是在各自的末尾的空节点处相等。为什么一定会相等呢，因为两个指针走过的路程相同，是两个链表的长度之和，所以一定会相等。这个思路真的很巧妙，而且更重要的是代码写起来特别的简洁，参见代码如下：
C++ 解法二：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return NULL;
ListNode *a = headA, *b = headB;
while (a != b) {
a = a ? a->next : headB;
b = b ? b->next : headA;
}
return a;
}
};
Java 解法二：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode a = headA, b = headB;
while (a != b) {
a = (a != null) ? a.next : headB;
b = (b != null) ? b.next : headA;
}
return a;
}
}
类似题目：
Minimum Index Sum of Two Lists
参考资料：
https://leetcode.com/problems/intersection-of-two-linked-lists/
到此这篇关于C++实现LeetCode(160.求两个链表的交点)的文章就介绍到这了,更多相关C++实现求两个链表的交点内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C++实现LeetCode(161.一个编辑距离)
[LeetCode] 161. One Edit Distance 一个编辑距离 Given two strings s and t, determine if they are both one edit distance apart. Note: There are 3 possiblities to satisify one edit distance apart: Insert a character into s to get t Delete a character from s
-
C++实现LeetCode(155.最小栈)
[LeetCode] 155. Min Stack 最小栈 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getM
-
C++实现LeetCode(157.用Read4来读取N个字符)
[LeetCode] 157. Read N Characters Given Read4 用Read4来读取N个字符 Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters. Method read4: The API read4 reads 4 consecutive characters from t
-
C++实现LeetCode(156.二叉树的上下颠倒)
[LeetCode] 156. Binary Tree Upside Down 二叉树的上下颠倒 Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the origina
-
C++实现LeetCode(159.最多有两个不同字符的最长子串)
[LeetCode] 159. Longest Substring with At Most Two Distinct Characters 最多有两个不同字符的最长子串 Given a string s , find the length of the longest substring t that contains at most 2 distinct characters. Example 1: Input: "eceba" Output: 3 Explanation: ti
-
C++实现LeetCode(154.寻找旋转有序数组的最小值之二)
[LeetCode] 154. Find Minimum in Rotated Sorted Array II 寻找旋转有序数组的最小值之二 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). Find the minimum element. Th
-
C++实现LeetCode(158.用Read4来读取N个字符之二 - 多次调用)
[LeetCode] 158. Read N Characters Given Read4 II - Call multiple times 用Read4来读取N个字符之二 - 多次调用 Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be ca
-
C++实现LeetCode(904.水果装入果篮)
[LeetCode] 904. Fruit Into Baskets 水果装入果篮 In a row of trees, the `i`-th tree produces fruit with type `tree[i]`. You start at any tree of your choice, then repeatedly perform the following steps: Add one piece of fruit from this tree to your baskets.
-
C++实现LeetCode(160.求两个链表的交点)
[LeetCode] 160.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
-
C++ 解决求两个链表的第一个公共结点问题
目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 题目描述: 输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空.(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的) 数据范围: n<=1000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示: 可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点. 输入描述: 输入分
-
C++ 解决求两个链表的第一个公共结点问题
目录 题目描述: 输入描述: 返回值描述: 示例: 解题思路: 补充 题目描述: 输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空.(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的) 数据范围: n<=1000 要求:空间复杂度 O(1),时间复杂度 O(n) 例如,输入{1,2,3},{4,5},{6,7}时,两个无环的单向链表的结构如下图所示: 可以看到它们的第一个公共结点的结点值为6,所以返回结点值为6的结点. 输入描述:
-
Python求两个圆的交点坐标或三个圆的交点坐标方法
计算两个圆的交点 代码如下: # -*- coding: utf-8 -*- import math import numpy as np def insec(p1,r1,p2,r2): x = p1[0] y = p1[1] R = r1 a = p2[0] b = p2[1] S = r2 d = math.sqrt((abs(a-x))**2 + (abs(b-y))**2) if d > (R+S) or d < (abs(R-S)): print ("Two circles
-
C++实现LeetCode(21.混合插入有序链表)
[LeetCode] 21. Merge Two Sorted Lists 混合插入有序链表 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. Example: Input: 1->2->4, 1->3->4 Output: 1->1->2
-
C++实现LeetCode(83.移除有序链表中的重复项)
[LeetCode] 83. Remove Duplicates from Sorted List 移除有序链表中的重复项 Given a sorted linked list, delete all duplicates such that each element appear only once. Example 1: Input: 1->1->2 Output: 1->2 Example 2: Input: 1->1->2->3->3 Output: 1-
-
C++实现LeetCode(187.求重复的DNA序列)
[LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr
-
C++实现LeetCode(124.求二叉树的最大路径和)
[LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child conn
-
C++实现LeetCode(129.求根到叶节点数字之和)
[LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum
-
C++实现LeetCode(128.求最长连续序列)
[LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl