LinkedList Problem 2

LinkedList_test_2.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-


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


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def r_append(self, data):
        node = Node(data)
        if self.tail is None:
            self.head = node
            self.tail = node
        else:
            node.next = self.head
            self.head = node

    def append(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def iter(self):
        if not self.head:
            return
        cur = self.head
        yield cur.data
        while cur.next:
            cur = cur.next
            yield cur.data

def mergeLinkedList(even_list, odd_list):
    linked_list = LinkedList()
    p = even_list.head
    q = odd_list.head
    while p != None or q != None:
        if p.data:
            linked_list.append(p.data)
            p = p.next
        if q.data:
            linked_list.append(q.data)
            q = q.next

    return linked_list

if __name__ == '__main__':

    odd_list = LinkedList()
    even_list = LinkedList()

    d = {}

    list_node = raw_input("eg: 3<->1\n")

    # 初始化
    while list_node != '':
        input_list = list_node.split('<->')
        if input_list[0] == 'null' or input_list[1] == 'null':
            # 奇数dict , 从尾部插入
            if input_list[1] == 'null':
                even_list.r_append(input_list[0])
            # 偶数 dict , 从头部插入
            if input_list[0] == 'null':
                odd_list.append(input_list[1])
        else:
            # 构造存储字典
            d[input_list[0]] = input_list[1]

        list_node = raw_input("eg: 3<->1\n")


    even_tail = even_list.tail.data
    odd_head = odd_list.head.data

    while d:
        try:
            even_list.r_append(d[even_tail])
            del d[even_tail]
        except KeyError:
            for k, v in d.items():
                if v == even_tail:
                    even_list.r_append(k)
                    del d[k]
        try:
            odd_list.append(d[odd_head])
            del d[odd_head]
        except KeyError:
            for k, v in d.items():
                if v == odd_head:
                    odd_list.r_append(k)
                    del d[k]

        even_tail = even_list.head.data
        odd_head = odd_list.tail.data

    # 合并链表
    final_list = mergeLinkedList(even_list, odd_list)

    for i in final_list.iter():
        print i