160-相交链表
访问量:984

一、题目

地址: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
}