LeetCode 160. Intersection of Two Linked Lists （两个链表的交点）

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.

题目标签：Linked List

　　题目给了我们两个链表，让我们找到它们是否有交点，返回那个交点。

　　试想一下，如果是两个长度相等的链表，那么我们只需要遍历链表，比较两个点是否相等就可以了。

　　所以，我们首先要得到两个链表的长度，如果不一样长，那么把长的链表先走，走到和另外一个链表一样长度的时候，开始比较两个点是否相等来找到交点；如果没有，那么最后就返回null。

　　如果两个链表有交点的话，那么从交点前一个点开始，两个链表从这里开始，之后的长度一定是相等的。

Java Solution:

Runtime beats 41.31%

完成日期：06/09/2017

关键词：singly-linked list

关键点：让更长的链表先走完多余的部分

 /**

  * 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)

     {

         ListNode cursor1 = headA;

         ListNode cursor2 = headB;

         int len1 = getListLength(cursor1);

         int len2 = getListLength(cursor2);

         if(len1 > len2)

         {

             for(int i=0; i<len1-len2;i++)

                 cursor1 = cursor1.next;

         }

         else if(len1 < len2)

         {

             for(int i=0; i<len2-len1;i++)

                 cursor2 = cursor2.next;

         }

         while(cursor1 != null)

         {

             if(cursor1 == cursor2)

                 return cursor1;

             cursor1 = cursor1.next;

             cursor2 = cursor2.next;

         }

         return null;

     }

     private int getListLength(ListNode head)

     {

         ListNode cursor = head;

         int len = 0;

         while(cursor != null)

         {

             cursor = cursor.next;

             len++;

         }

         return len;

     }

 }

参考资料：N/A

LeetCode 题目列表 - LeetCode Questions List

题目来源：https://leetcode.com/

巴特西

LeetCode 160. Intersection of Two Linked Lists （两个链表的交点）

最新文章

热门文章