Python

Question

我正在研究接受链表作为输入的问题，此时我什至不知道如何设置示例链表。

我最初的问题是理解以下指令：

Write a function that accepts a linked list as input, then reverses that linked list.

这是否简单地涉及将 'reversing summary' 定义为以下内容的一部分，或者是否有一些其他方式来总结 Python 中的链表：

class Node(object):

    # Initialize with a single datum and pointer set to None

    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    # Returns the stored data

    def get_data(self):
        return self.data

    # Returns the next node

    def get_next(self):
        return self.next_node

    # Reset the pointer to a new node

    def set_next(self, new_next):
        self.next_node = new_next

    def set_data(self, data):
        self.data = data

class LinkedList(object):

    # Top node in the list created on __init__

    def __init__(self, head=None):
        self.head = head

    # Take in the new node and point the new node to the prior head O(1)

    def insert(self, data):
        new_node = Node(data)
        new_node.set_next(self.head)
        self.head = new_node

    # Counts nodes O(n)

    def size(self):
        current = self.head
        count = 0
        while current:
            count += 1
            current = current.get_next()
        return count

    # Checks each node for requested data O(n)

    def search(self, data):
        current = self.head
        found = False
        while current and found is False:
            if current.get_data() == data:
                found = True
            else:
                current = current.get_next()
        if current is None:
            raise ValueError("Data not in list")
        return current

    # Similar to search, leapfrogs to delete, resetting previous node pointer to point to the next node in line O(n)

    def delete(self, data):
        current = self.head
        previous = None
        found = False
        while current and found is False:
            if current.get_data() == data:
                found = True
            else:
                previous = current
                current = current.get_next()
        if current is None:
            raise ValueError("Data not in list")
        if previous is None:
            self.head = current.get_next()
        else:
            previous.set_next(current.get_next())

Answer 1

您的基本链表 class 的所有代码似乎都在那里。您只需要反转您的链接列表。反转链表如下。

[1] -> [2] -> [3] -> NULL

你可以看出 1 是 Head，3 是 Tail（意思是它是链表中的最后一个节点，因为它指向 NULL 或 Python 中的 None）。您需要做的是找出一些算法来获取该链表并产生此结果。

[3] -> [2] -> [1] -> NULL

现在 3 是头，1 是尾。

所以使用伪代码：

Initalize 3 Nodes: prev, next, and current
current = head
prev = None
next = None
While current != None
    next = current.next
    current.next = prev
    prev = current
    current = next
head = prev

Python - 反转链表 class 模块作为输入

Python - reversing a linked list class module as input

methods

function

linked-list

inner-classes