①中文题目
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
在节点 c1 开始相交。
注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
②思路
遍历,O(M*N)的遍历,直到找出相等的结点(不是val相等)
③我的代码(很慢)
1 public class Solution { 2 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 3 ListNode temp1=headA; 4 ListNode temp2=headB; 5 if(temp1==null||temp2==null) 6 return null; 7 while(temp1!=null){ 8 if(temp2==null){ //当temp2遍历到尾巴的时候, 9 temp1=temp1.next; //temp1后移1位 10 temp2=headB; //temp2回到自己原本的头部,再来一遍 11 } 12 if(temp1==temp2) 13 return temp1; 14 temp2=temp2.next; //这一次比较,没找到相等的,于是temp2后移一步 15 } 16 return null; 17 } 18 }
④运行结果
执行结果:通过 。显示详情
执行用时 :674 ms, 在所有 Java 提交中击败了5.01%的用户
内存消耗 :48.5 MB, 在所有 Java 提交中击败了5.05%的用户
⑤别人的快速代码
1 public class Solution { 2 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 3 if (headA == null || headB == null) return null; 4 ListNode pA = headA, pB = headB; 5 while (pA != pB) { 6 pA = pA == null ? headB : pA.next; 7 pB = pB == null ? headA : pB.next; 8 } 9 return pA; 10 } 11 }
他的运行结果:
执行结果:
通过
显示详情
执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :37.5 MB, 在所有 Java 提交中击败了85.92%的用户
他的思路:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/。太厉害了。
⑥学到的知识
1、我自己的代码里,12行,不是val元素相等,而是要判断结点是否相等(结点包括元素和指针)
2、看看别人的代码里的思路,太厉害了。还给出了图解!