[LeetCode] 判断两个链表是否有公共节点并返回第一个公共节点

来源:互联网 发布:手机淘宝怎么追加评价 编辑:IT博客网 时间:2019/09/17 14:17

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.

这题就是说判断两个链表是否有公共节点,如果有,返回第一个公共节点。

分析:如果两条链表有公共节点,则这个条链表的最后一个节点一定相同,这应该是解题的关键。所以第一步就是首先判断链表有没有公共点,其二,如果链表有公共点,则该点之后的两条链表长度一定相同,所以第二部就是先让较长的链表先走abs(lenA - lenB)步,这样一来,开始判断的部分长度一定相等。


[python] view plaincopy
  1. class ListNode:  
  2.      def __init__(self, x):  
  3.          self.val = x  
  4.          self.next = None  
  5.   
  6. class Solution:  
  7.     # @param two ListNodes  
  8.     # @return the intersected ListNode  
  9.     def getIntersectionNode(self, headA, headB):  
  10.         lastA = headA  
  11.         lastB = headB  
  12.         lenA = 0  
  13.         lenB = 0  
  14.         if None == headA or None == headB:  
  15.             return None  
  16.         while lastA.next != None:  
  17.             lastA = lastA.next  
  18.             lenA += 1  
  19.               
  20.         while lastB.next != None:  
  21.             lastB = lastB.next  
  22.             lenB += 1  
  23.         if lastA != lastB:  
  24.             return None  
  25.           
  26.         p = headA  
  27.         q = headB  
  28.         for i in xrange(lenA - lenB):  
  29.             p = p.next  
  30.         for i in xrange(lenB - lenA):  
  31.             q = q.next  
  32.           
  33.         while p != None:  
  34.             if p == q:  
  35.                 return p;  
  36.             p = p.next  
  37.             q = q.next  
  38.         return None  
  39.           
  40. sol = Solution()  
  41. a1 = ListNode(0)  
  42. a2 = ListNode(1)  
  43. a3 = ListNode(2)  
  44. a4 = ListNode(33)  
  45.   
  46. b1 = ListNode(8)  
  47. b2 = ListNode(6)  
  48.   
  49. a1.next = a2  
  50. a2.next = a3  
  51. a3.next = a4  
  52.   
  53. b1.next = b2  
  54. b2.next = a3  
  55.   
  56. node = sol.getIntersectionNode(a1, b1)  
  57. while node != None:  
  58.     print("%d" % node.val)  
  59.     node = node.next  
0 0