Write a program to find the node at which the intersection of two singly linked lists begins.
1 | For example, the following two linked lists : |
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)的内存空间。
思路:
方法一:
如果两个链表相交,先用 countA=0, countB=0统计两个单链表的长度,因为如果二者有交点的话,如example中所示,二者的后半部分是相同的,成“Y”字形,所以只要减去长的单链表中和短单链表相差的元素个数,然后再同时让两个单链表向后移动,则当二者相同时就是二者的交点。
1 | ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { |
方法二:
不用整形变量值来记录哪个链表长,而是利用指针的移动差来重新设定除去长链表中的元素的头结点,然后再移动比较,当相等时就是要查找的第一个相同的节点。其实查找相同节点的方法是和上面一样的,但是找元素差不同。首先当A链表指针pA遍历到尾节点之后为空的话,就让其指向B链表头,如果B链表指针pB遍历到尾节点之后为空的话,就让其指向A链表头,这样交换,让二者相等相与的时候肯定是两个链表的开始节点。
1 | ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { |