LeetCode OJ 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.

这个题目是要找出两个链表的交叉点，该如何解决呢？如果两个链表相交，我们从A链表出发移动一段距离alen，出B列表出发移动一段距离blen，那么会发现他们指向同一个节点c1。那么这个距离是多少呢？

我们把每一个链表看成两段，不相交的一段和相交的一段。相交的一段对于两个链表长度是一样的，不想交的一段链表的长度是不同的。如果我们分别计算出两个链表的长度，然后计算他们长度的差值f，然后在较长的链表上先移动距离f，再同时从A,B链表出发开始遍历，若发现他们指向同一个节点，则他们相交并返回相交的点，若他们不想交，则会遍历到链表的尾部，则返回null。代码如下：

 /**

  * 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 p1 = headA, p2 = headB;

         int len1 = 0, len2 = 0;

         while (p1 != null) {    //求链表A的长度

             p1 = p1.next;

             len1++;

         }

         while (p2 != null) {    //求链表B的长度

             p2 = p2.next;

             len2++;

         }

         p1 = headA;

         p2 = headB;

         if (len1 > len2) {      //计算链表长度的差值并在较长的链表上向后移动|len1-len2|

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

                 p1 = p1.next;

             }

         } else {

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

                 p2 = p2.next;

             }

         }

         while (p1 != p2) {      //向后遍历链表A和链表B，找到相交的节点，若遍历到最后，返回null

             p1 = p1.next;

             p2 = p2.next;

         }

         return p1;

     }

 }

巴特西

LeetCode OJ 160. Intersection of Two Linked Lists

最新文章

热门文章