将节点移动到节点链的末端

Question

我有一个函数，我必须移动一个现有的代码，例如

def print_chain_and_ids(chain):
    current = chain
    while current != None:
        print(id(current), current.get_data())
        current = current.get_next()

a = Node('first')
b = Node('middle')
c = Node('last')
a.set_next(b)
b.set_next(c)

print_chain_and_ids(a)
move_node_to_end(a, 'middle')    

print_chain_and_ids(a)

所以现在的链条是：

a ----> b ----> c

节点c位于链的末尾。在

如果我想将节点b移动到链的末尾，那么它将：

a ----> c ----> b

所以它不会改变最后一个节点的值，而只是移动它。我准备好了一个节点类：

^{pr2}$

我想知道我该怎么做。在

我要做一个函数，它需要两个输入，第一个节点，还有移动到链最后一个位置的值。所以：

def node_to_end(first_node, value_to_move):
    .....

这是我必须修改节点位置的地方。所以要移动的值移到最后一个位置。在

a = Node('blue')
b = Node('red')
c = Node('green')

a.set_next(b)
b.set_next(c)

会导致blue red green

node_to_end(a, 'red') 

会产生一系列

blue green red

谢谢你的帮助。在

Answer 1

这需要一些计算。让我们假设一般情况：

e_i-1->；e_i->；e_i+1->。。。->；e_n

现在我们要将e_i移到最后一个位置：

e_i-1->；e_i+1->。。。->；e_n->；e_i

所以问题是：应该改变什么？根据一般情况，有三个指针必须更改：

• e_i-1现在指向e_i+1
• e_i现在指向任何东西（None）；并且
• e_n现在指向e_i。在

现在，由于链表是非双重链接的：一个节点没有对前一个节点的引用，所以我们唯一能做的就是从根节点开始迭代直到找到元素：

def get_prev_element(root,node):
    while root.get_next() is not node:
        root = root.get_next()

一旦我们有了上一个元素，我们就可以让它链接到下一个元素：

^{pr2}$

但现在我们还是要找出最后一个元素是什么。你猜怎么着，我们再次这样做，通过迭代，我们可以从我们自己的节点开始：

def get_last(node):
    while node.get_next() is not None:
        node = node.get_next()
    return node

现在我们将最后一个节点的next设置为我们自己的节点：

last.set_next(node)

最后，我们在None旁边设置了自己的：

node.set_next(None)

现在，我们可以在节点上定义一个方法：

class Node:

    # ...

    def get_previous(self,root):
        previous = root
        while previous.get_next() is not self:
            previous = previous.get_next()
        return previous

    def get_last(self):
        last = self
        while last.get_next() is not None:
            last = last.get_next()
        return last

    def move_last(self,root):
        previous = self.get_previous(root)
        previous.set_next(self.get_next())
        last = self.get_last()
        last.set_next(self)
        self.set_next(None)

请注意，由于链表不是双重链接的，因此必须给它根元素。在

---

Intermezzo：如果你有对a，b和{}的引用。当然，没有理由计算previous和last：您知道a是previous，而{}是最后一个。所以在这种情况下，代码就是：

a.set_next(c)
c.set_next(b)
b.set_next(None)

---

如果根元素是节点本身，则该代码不起作用。我把它作为一个练习来修改代码以使其正常工作。这并不难。在

Answer 2

你的节点链非常类似于所谓的单链链表。使用这些方法，节点通常在沿着列表遍历时跟踪上一个节点，这样当找到目标节点时，您就会知道哪个节点（如果有的话）出现在它之前。有了这些信息，就可以很容易地修改列表。在

下面是如何将其应用到代码中。我还添加了一个小实用程序来打印链的内容，以明确其中的内容。在

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

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next

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

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

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

def move_to_end(start, target):
    """Move target node from the chain beginning with start to end."""
    previous = None
    current = start
    while current:
        if current.get_next() is target:
            previous = current
            break
        current = current.get_next()

    if previous:  # target found in chain?
        previous.set_next(target.get_next())  # remove it
        # and move it to the end
        current = target
        while current:
            if not current.get_next():  # last node in chain?
                target.set_next(None)
                current.set_next(target)
                break
            current = current.get_next()

def print_node_chain(start):
    """Utility to print out a node chain starting from given node."""
    values = []
    current = start
    while current:
        values.append(str(current))
        current = current.get_next()

    print('   > '.join(values) + '   > None')

a = Node('blue')
b = Node('red')
c = Node('green')

a.set_next(b)
b.set_next(c)

print_node_chain(a)
move_to_end(a, b)
print_node_chain(a)

输出：

^{pr2}$