Pythonプログラマー面接アルゴリズム宝典---解題まとめ:第1章チェーンテーブル1.4チェーンテーブルを並べ替える方法

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

'''
Python         ---    :  1     1.4            

  :
    L0->L1->...Ln-1->Ln，        L0->Ln->L1->Ln-1->L2->Ln-2...。
  :
(1)              ，         ；
(2)        next ，       。

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

  2:
       ，         ，
                                   。
            :
          :
R1->R2->...->Rn
              ，          :
n/2       -1

        :
  ： n/2       -1           ，               ；
       ，
  ，  n   ，      n/2              
  ，     n/2 + 1              
               ，
                 ，       ，
    。

  :
1      +   
  ： n/2       -1           ，               ；
       ，
  ，  n   ，      n/2              
  ，     n/2 + 1              
               ，
                 ，       ，
    。

2   
    #                  
    frontBeginNode = head
    frontNextNode = frontBeginNode.nextNode if frontBeginNode else None
    laterNextNode = laterBeginNode.nextNode if laterBeginNode else None
    middleNode = currNode
    while laterBeginNode:
          :                ，       ，
               
        if laterBeginNode == frontNextNode:
            break
        laterBeginNode.nextNode = frontNextNode
        frontBeginNode.nextNode = laterBeginNode
                                           
        middleNode.nextNode = laterNextNode
        frontBeginNode = frontNextNode
        laterBeginNode = laterNextNode
        frontNextNode = frontBeginNode.nextNode if frontBeginNode else None
        laterNextNode = laterBeginNode.nextNode if laterBeginNode else None
    return head

  :
Python         
'''

class Node(object):
    def __init__(self, data=None, nextNode=None):
        self.data = data
        self.nextNode = nextNode

def buildList(arr):
    if not arr:
        return
    head = Node(arr[0])
    currNode = head
    for i, data in enumerate(arr):
        if 0 == i:
            continue
        newNode = Node(data)
        currNode.nextNode = newNode
        currNode = newNode
    return head

def printList(head):
    if not head:
        return
    currNode = head
    while currNode:
        print currNode.data
        currNode = currNode.nextNode


def getListLength(head):
    length = 0
    currNode = head
    while currNode:
        length += 1
        currNode = currNode.nextNode
    return length

'''
  ： n/2       -1           ，               ；
       ，
   :
  n   ，       : n/2 - 1
  ，      : n/2
  ，  n   ，      n/2              
  ，     n/2 + 1              
'''
def sortList(head):
    temp = head
    length = getListLength(temp)
    # print length
    if length in set([0, 1, 2]):
        return head
    # print "#############"
    # printList(head)
    if length % 2 == 0:
        findIndex = length / 2 - 1
    else:
        findIndex = length / 2
    currNode = head
    counter = 0
    while currNode:
        if counter == findIndex:
            break
        currNode = currNode.nextNode
        counter += 1
    # print "          : {counter}".format(counter=counter)
    #         
    reverseList(currNode)
    laterBeginNode = currNode.nextNode if currNode else None
    #                  
    frontBeginNode = head
    frontNextNode = frontBeginNode.nextNode if frontBeginNode else None
    laterNextNode = laterBeginNode.nextNode if laterBeginNode else None
    middleNode = currNode
    while laterBeginNode:
        '''
          :                ，       ，
               
       '''
        if laterBeginNode == frontNextNode:
            break
        laterBeginNode.nextNode = frontNextNode
        frontBeginNode.nextNode = laterBeginNode
        '''
                                           
       '''
        middleNode.nextNode = laterNextNode
        frontBeginNode = frontNextNode
        laterBeginNode = laterNextNode
        frontNextNode = frontBeginNode.nextNode if frontBeginNode else None
        laterNextNode = laterBeginNode.nextNode if laterBeginNode else None
    return head


def reverseList(head):
    if not head:
        return head
    if head.nextNode is None:
        return head
    if head.nextNode.nextNode is None:
        return head
    currentNode = head.nextNode.nextNode
    nextNode = currentNode.nextNode
    '''
          ，         nextNode None
    '''
    head.nextNode.nextNode = None
    while currentNode:
        currentNode.nextNode = head.nextNode
        head.nextNode = currentNode
        currentNode = nextNode
        nextNode = nextNode.nextNode if nextNode else None
    return head


def process():
    arr = (i for i in range(5))
    head = buildList(list(arr))
    # printList(head)
    # sortList(head)
    # newHead = reverseList(head)
    # printList(newHead)
    newHead = sortList(head)
    printList(newHead)

    print "#########"
    arr = (i for i in range(4))
    head = buildList(list(arr))
    newHead = sortList(head)
    printList(newHead)

    print "#########"
    arr = (i for i in range(3))
    head = buildList(list(arr))
    newHead = sortList(head)
    printList(newHead)

    print "#########"
    arr = (i for i in range(2))
    head = buildList(list(arr))
    newHead = sortList(head)
    printList(newHead)

    print "#########"
    arr = (i for i in range(1))
    head = buildList(list(arr))
    newHead = sortList(head)
    printList(newHead)

    print "#########"
    arr = (i for i in range(0))
    head = buildList(list(arr))
    newHead = sortList(head)
    printList(newHead)

if __name__ == "__main__":
    process()