(LeetCode 160)Intersection of Two Linked Lists
LeetCode of 160 two Linked lists intersection
2023-09-14 08:59:06 时间
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
要求O(n)的时间复杂度和O(1)的空间复杂度
解题思路:
1、如果不考虑空间复杂度,可以用set容器记录第一个链表的所有结点,依次遍历第二个链表,第一个存在set中的结点即为交点,否则不存在。
2、第一个链表长为x,第二个链表长为y,假设x>y,让第一个链表指针先走x-y步,(这样两个链表指针就长度对齐),然后两个链表指针一起走,如果遇到对应相等,则为交点,否则不存在。
代码:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: int getLength(ListNode *head){ int i=0; for(ListNode *p=head;p!=NULL;p=p->next) i++; return i; } ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if(headA==NULL || headB==NULL) return NULL; int lenA=0,lenB=0; ListNode *pA,*pB; pA=headA; pB=headB; lenA=getLength(pA); lenB=getLength(pB); if(lenA>lenB){ for(int i=lenA-lenB;i>0;i--) pA=pA->next; } if(lenB>lenA){ for(int i=lenB-lenA;i>0;i--) pB=pB->next; } while(pA!=pB){ pA=pA->next; pB=pB->next; } if(pA==pB) return pA; else return NULL; } };
相关文章
- Leetcode 之Length of Last Word(37)
- Leetcode 之Wildcard Matching(32)
- leetcode 之Remove Nth Node From End of List(19)
- Java实现 LeetCode 621 任务调度器(暴力大法)
- Java实现 LeetCode 509 斐波那契数
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- Java实现LeetCode_0026_RemoveDuplicatesFromSortedArray
- 【LeetCode算法-58/66】Length of Last Word/Plus One
- [Javascript] Use an Array of Promises with a For Await Of Loop
- LeetCode(19):删除链表的倒数第N个节点
- [LeetCode] Reverse Vowels of a String
- [LeetCode] Number of 1 Bits
- LeetCode-1441. 用栈操作构建数组【哈希表,栈,数组,模拟】
- Python 刷Leetcode题库,顺带学英语单词(37)
- [LeetCode]235.Lowest Common Ancestor of a Binary Search Tree
- leetcode 题解 || Remove Nth Node From End of List 问题
- Leetcode 1390. 四因数
- [LeetCode] 287. 寻找重复数 ☆☆☆
- [LeetCode] 231. Power of Two ☆(是否2 的幂)
- [LeetCode] 191. Number of 1 Bits ☆(位 1 的个数)
- [LeetCode] 111. Minimum Depth of Binary Tree ☆(二叉树的最小深度)
- 【LeetCode】【Python题解】Single Number & Maximum Depth of Binary Tree
- leetcode 559. Maximum Depth of N-ary Tree
- leetcode 326. Power of Three
- leetcode 231. Power of Two
- leetcode 350. Intersection of Two Arrays II
- leetcode 599. Minimum Index Sum of Two Lists
- leetcode 697. Degree of an Array
- leetcode 762. Prime Number of Set Bits in Binary Representation
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
- 【LeetCode】94. 二叉树的中序遍历