一、题目

地址：https://leetcode.com/problems/intersection-of-two-linked-lists/submissions/

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

注意：

如果两个链表没有交点，返回 null.

在返回结果后，两个链表仍须保持原有的结构。

可假定整个链表结构中没有循环。

程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

交点，不是当前节点的值相同，而是两个节点的地址相同。

二、解法

1、解法一

思路：以其中一个链表headbB为主，另外一个链表headbA循环。从headbB中第一个节点开始，逐次判断，是否满足要求。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
   if headB ==nil || headA == nil {
      return nil
   }

   var p0, pA, pB *ListNode
   pA = headA
   pB = headB

   for  {
      if pB == nil {
         break
      }

      if pA == nil {
         pA = headA
         pB = pB.Next
      }

      if pA != pB {
         p0 = nil
      } else  {
         pB = pB.Next
         if p0 == nil {
            p0 = pA
         }
      }

      pA = pA.Next
   }

   return  p0
}

1、解法二

思路：如果链表是双向链表，那么这道题目就会变得特别简单，因为我们可以从后往前比较，可惜，不是哈。但是我们可以先计算链表长度，然后排除不需要比较的部分，如下图，链表1,前面一部分是不需要比较的。

func getIntersectionNode(headA, headB *ListNode) *ListNode {
   if headB ==nil || headA == nil {
      return nil
   }

   pA := headA
   pB := headB

   var i,j int

   for pA != nil {
      i ++

      pA = pA.Next
   }

   for pB != nil {
      j ++
      pB = pB.Next
   }

   var k int
   // pA 为长链， pB为短链
   if i >= j {
      pA = headA
      pB = headB
      k = i - j
   } else {
      pA = headB
      pB = headA
      k = j -i
   }

   for k > 0  {
      pA = pA.Next
      k--
   }

   for pA != pB {
      if pA == nil || pB == nil {
         break
      }

      pA = pA.Next
      pB = pB.Next
   }

   return  pA
}