Pythonプログラマー面接アルゴリズム宝典---解題まとめ:第1章チェーンテーブル1.11 2 2つのチェーンテーブル(ループなし)が交差しているかどうかをどのように判断するか

#!/usr/bin/env python
# encoding: utf-8

'''
Python         ---    :  1     1.11         (  )    

  :
                     ，     :
head1->1->2->3->4
                    ->5->6->7
head2->1->2->3->4
    ，          5，            ，    ，        。

  :
  1:
                    ，              ，             。
      ，           ，
                   ，    ，        ；
            ，        ，                       。
    :          。

  2:
        1    L1,   2    L2
     ，                   。
  L1 > L2, dis=L1 - L2,
   1  dis ，         ，            ；
  ， dis = L2 - L1
   2  dis ，         ，            。
         ：
           ，              。

  :
             ，     2，  1          ，
      1.

      :
 。

      :
         ，        ，          ，
          ，        ，         
   。
                      。
    ：
        :
head1->1->3->5->7->9
        :
head2->2->4->6->7->9
           7
       :
    2     1   ，  
head1->1->3->5->7->9->head2->2->4->6->7->9
        curr1,  head1,   1 
      curr2,  head1，   2 
          :
head1   ->1 ->3 ->5 ->7 ->9 ->head2 ->2 ->4 ->6 ->7 ->9
              7，9         7，9     ，       2  7，9  ，         :
head1   ->1 ->3 ->5 ->7 ->9 ->head2 ->2 ->4 ->6
                                              |
                     1 ->3 ->5 ->7 ->9 ->2 ->4 ->6
                                     |
                     " + str(current.data)
        current = current.nextNode
    print result


def construstIntersectList(head1, head2, meetValue):
    if not head1 or not head2 or meetValue is None:
        return
    meetNode = head1.nextNode
    while meetNode:
        if meetNode.data == meetValue:
            break
        meetNode = meetNode.nextNode
    prev = head2
    curr = head2.nextNode
    while curr:
        if curr.data == meetValue:
            prev.nextNode = meetNode
            break
        prev = curr
        curr = curr.nextNode


def mergeTwoList(head1, head2):
    if not head1 and not head2:
        return head1
    elif not head1:
        return head2
    elif not head2:
        return head1
    prev = head1
    curr = head1.nextNode
    while curr:
        prev = curr
        curr = curr.nextNode
    prev.nextNode = head2.nextNode
    return head1


def isIntersected(head1, head2):
    if not head1 or not head2 or not head1.nextNode or not head2.nextNode:
        return
    newHead = mergeTwoList(head1, head2)
    fast = newHead.nextNode
    slow = newHead.nextNode
    while fast:
        fast = fast.nextNode.nextNode if fast.nextNode else None
        slow = slow.nextNode
        if fast == slow:
            return slow
    return


def findLoopBegin(head, meetNode):
    if not head or not head.nextNode or not meetNode:
        return
    first = head.nextNode
    second = meetNode
    while second:
        if first == second:
            return first
        first = first.nextNode
        second = second.nextNode
    return


def process():
    arr1 = [1, 3, 5, 7, 9]
    arr2 = [2, 4, 6, 7, 9]
    head1 = buildList(arr1)
    head2 = buildList(arr2)
    construstIntersectList(head1, head2, 7)
    printList(head1)
    printList(head2)
    result = isIntersected(head1, head2)
    if result != None:
        print "Intersect"
    else:
        print "Not Intersect"
    beginLoopNode = findLoopBegin(head1, result)
    print beginLoopNode.data if beginLoopNode else ""


if __name__ == "__main__":
    process()