①中文题目

编写一个程序,找到两个单链表相交的起始节点。

如下面的两个链表:

在节点 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、看看别人的代码里的思路,太厉害了。还给出了图解!

02-13 22:20