old_contents: http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=135449&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
  
  两个链表 求最大的公共后缀
  
  class ListNode:
      def __init__(self, value):
          self.value = value
          self.next = None
  
  def find_max_postfix(head1, head2):
      if not head1 or not head2: return None
      head1 = reverse_linkedlist(head1)
      head2 = reverse_linkedlist(head2)
      dummy = ListNode(0)
      result = dummy
  
      while head1 and head2:
          if head1.value == head2.value:
              tmp = head1.next  # Note bug here, we need to save the tmp, otherwise, head1.next will become None ! 
              result.next = head1
              result = result.next
              result.next = None 
              
              head1 = tmp
              head2 = head2.next
          else:
              break
      
      return dummy.next
      
  def reverse_linkedlist(head1):
      pre = None
      cur = head1
      while cur:
          next = cur.next
          cur.next = pre
          pre = cur 
          cur = next
      return pre
  
  def print_list(head):
      while head:
          print "head.val: ", head.value
          head = head.next 
  
  
new_contents: '''
  http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=135449&extra=page%3D1%26filter%3Dsortid%26sortid%3D311%26sortid%3D311
  
  1. 两个链表 求最大的公共后缀
  '''
  
  class ListNode:
      def __init__(self, value):
          self.value = value
          self.next = None
  
  def find_max_postfix(head1, head2):
      if not head1 or not head2: return None
      head1 = reverse_linkedlist(head1)
      head2 = reverse_linkedlist(head2)
      dummy = ListNode(0)
      result = dummy
  
      while head1 and head2:
          if head1.value == head2.value:
              tmp = head1.next  # Note bug here, we need to save the tmp, otherwise, head1.next will become None ! 
              result.next = head1
              result = result.next
              result.next = None 
              
              head1 = tmp
              head2 = head2.next
          else:
              break
      
      return dummy.next
      
  def reverse_linkedlist(head1):
      pre = None
      cur = head1
      while cur:
          next = cur.next
          cur.next = pre
          pre = cur 
          cur = next
      return pre
  
  def print_list(head):
      while head:
          print "head.val: ", head.value
          head = head.next 
  
  
  '''
  2. permutations of a list without adjacent equal elements
  '''
  
  import collections
  import heapq
  
  def permutation_number(s):
      counts = collections.Counter(s)
      heap = [(-count, key) for key, count in counts.items()]
      heapq.heapify(heap)
      output = []
      last = None
      while heap:
          minuscount1, key1 = heapq.heappop(heap)
          if key1 != last or not heap:
              last = key1
              minuscount1 += 1
          else:
              minuscount2, key2 = heapq.heappop(heap)
              last = key2
              minuscount2 += 1
              if minuscount2 != 0:
                  heapq.heappush(heap, (minuscount2, key2))
          output.append(last)
          if minuscount1 != 0:
              heapq.heappush(heap, (minuscount1, key1))
      return ''.join(output)
  
  test1 = 'aaabbbccc'
  test2 = 'aaaaaaaabbbddd'
  print permutation_number(test1)
  print permutation_number(test2)
  
  
  # Best Reference: http://stackoverflow.com/questions/25285792/generate-all-permutations-of-a-list-without-adjacent-equal-elements
  
  
  
  
subject: Update google_面经.py