python-链表实现

Question

实现并测试以下链表方法

def intersection(self, rs):
    """
    -------------------------------------------------------
    Copies only the values common to both the current list and rs
    to a new list. Uses a looping algorithm.
    -------------------------------------------------------
    Preconditions:
        rs - another list (List)
    Postconditions:
        returns
        new_list - contains one copy of values common to current list
            and rs (List)
        Current list and rs are unchanged.
    -------------------------------------------------------
    """

class _ListNode:
    def __init__(self, value, next_):
        self._value = deepcopy(value)
        self._next = next_
        return

class List:
    def __init__(self):
        self._front = None
        self._count = 0
        return
    def is_empty(self):
        return self._front is None
    def __len__(self):
       return self._count
    def insert(self, i, value):
        if i < 0:
            # negative index
            i = self._count + i
        n = 0
        previous = None
        current = self._front

        while n < i and current is not None:
            previous = current
            current = current._next
            n += 1
        if previous is None:
            self._front = _ListNode(value, self._front)
        else:
            previous._next = _ListNode(value, current)
        self._count += 1
        return

到目前为止，我所拥有的，我现在不知道如何实现交集方法

例：

If List a contains:
0, 2, 1, 3, 5, 7

and List b contains:
1, 1, 3, 3, 5, 5, 7, 7

Then a.intersection(b) returns a List containing:
7, 5, 3, 1

Answer 1

添加一个__contains__，让你的生活更轻松一点

def __contains__(self, val):
    curr = self.front
    while curr is not None:
        if curr._value == val: return True
        curr = curr._next
    return False

def intersection(self, rs):
    answer = List()
    curr = self.front
    while curr is not None:
        if curr._value in rs: answer.insert(-1, curr._value)
    return answer

与递归的交集：

def extend(self, rs):
    curr = rs.front
    while curr is not None:
        self.insert(-1, curr._value)
def intersection(self, rs):
    if rs.front is None: return List()
    answer = self.intersection(rs.front._next)
    if rs.front._value in self: answer.insert(-1, rs.front._value)
    return answer