每天一道leetcode160-相交链表

• 2019 年 10 月 4 日
• 筆記

leetcode160-相交链表

中文链接：

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

英文链接：

https://leetcode.com/problems/intersection-of-two-linked-lists/

题目详述

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

例如，下面的两个链表：

A:          a1 → a2    c1 → c2 → c3    B:     b1 → b2 → b3

在节点 c1 开始相交。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

题目详解

思路

1. 如果两个链表有共同的节点，那么就是可以先分别计算两个链表的长度。
2. 两个链表是A和B，如果A的·长度比B的长，长度差是C，那么A就先从头结点走个长度差C，这样两者的长度就一样长了；
3. 然后两者一起进行遍历，直到找到的节点是相同的节点，那么循环结束，找到这个节点，返回即可。

代码

/**   * Definition for singly-linked list.   * public class ListNode {   *     int val;   *     ListNode next;   *     ListNode(int x) {   *         val = x;   *         next = null;   *     }   * }   */  public class Solution {      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {          int lengthA = 0;          int lengthB = 0;          ListNode tempA = headA;          ListNode tempB = headB;          while(tempA != null)          {              lengthA++;              tempA = tempA.next;          }          while(tempB != null)          {              lengthB++;              tempB = tempB.next;          }          tempA = headA;          tempB = headB;          if(lengthB > lengthA)          {              int cha = lengthB - lengthA;              for(int i=0;i<cha&&tempB != null;i++)                  tempB = tempB.next;          }else{              int cha = lengthA - lengthB;              for(int i=0;i<cha&&tempA != null;i++)                  tempA = tempA.next;          }          while(tempA != null && tempB != null && tempA  != tempB)          {              tempA = tempA.next;              tempB = tempB.next;          }          return tempA;      }  }  

代码讲解

1. 18到27行，去求A和B链表的长度；
2. 30-39行，A与B那个长度长，如果B长度长，那么B就去先走长度差，直到B与A的长度一样，如果A长度长也同理
3. 40行到44行，A与B一起遍历，直到找到相同的节点，然后输出