python-3.x - 在 Python 中实现链表

Question

我正在尝试实现此链接中找到的 leetcode 链表问题的两种解决方案： https ://leetcode.com/problems/middle-of-the-linked-list/solution/但我不能。到目前为止，我写的是以下内容：

第一个解决方案

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def middleNode(self, head):
        while arr[-1].next:
        arr.append(arr[-1].next)
    return arr[len(arr) // 2]


node =ListNode([1,2,3,4,5])

a.next = b

b.next = c

c.next = d

print(ListNode.middleNode())

第二种解决方案

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
   def middleNode(self, head)
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


a = ListNode(1)
b = ListNode(2)
c = ListNode(3)
d = ListNode(4)

a.next = b
b.next = c
c.next = d

my_list = Solution()

print(my_list.middleNode([1,2,3,4,5]))

标签： python-3.xlist

Answer 1

也许这会有所帮助。

class ListIsEmptyException(Exception):
    pass


class Node(object):

    def __init__(self, value, next=None):
        self._value = value
        self._next = next

    def __str__(self):
        return str(self._value)


class List(object):

    def __init__(self):
        self._head = self._tail = None

    def add_first(self, value):
        node = Node(value)
        if self._head is None:
            self._head = self._tail = node
        else:
            node._next = self._head
            self._head = node

    def add_last(self, value):
        node = Node(value)
        if self._tail is None:
            self._head = self._tail = node
        else:
            self._tail._next = node
            self._tail = node

    def get_first(self):
        if self._head is None:
            raise ListIsEmptyException
        return self._head

    def get_last(self):
        if self._tail is None:
            raise ListIsEmptyException
        return self._tail

    def remove_first(self):
        if self._head is None:
            raise ListIsEmptyException
        elif self._head._next is None:
            self._head = self._tail = None
        else:
            self._head = self._head._next

    def remove_last(self):
        if self._tail is None:
            raise ListIsEmptyException
        elif self._head._next is None:
            self._head = self._tail = None
        else:
            current = self._head
            while current._next != self._tail:
                current = current._next
            current._next = None

    def __len__(self):
        current = self._head
        i = 0
        while current is not None:
            i += 1
            current = current._next
        return i

    def __iter__(self):
        current = self._head
        while current is not None:
            yield current
            current = current._next


if __name__ == '__main__':
    lista = List()

    lista.add_first("A")
    lista.add_first("B")
    lista.add_last("C")

    for l in lista:
        print(l)