在deque中交换2个节点，python

Question

我试图交换两个不相邻的节点。而且，它们不是前或后节点，因此它们的前一个或下一个指针不是无。Python没有指针，但为了方便起见，我将前面和后面对节点节点的引用作为其指针。 但是，我遇到的问题是，即使切换成功，以前的指针引用也会被搞乱。这里，l是左节点，r是右节点。在

def _swap(self, l, r):
    assert l is not None and r is not None, "nodes to swap cannot be None"

    temp = l._prev._next
    l._prev._next = r._prev._next
    r._prev._next = temp
    temp = l._next
    l._next = r._next
    r._next = temp
    temp = l._prev
    l._prev = r._prev
    r._prev = temp

    return

交换前列表：4 5 2 7 1 8
交换前向后列出：8 1 7 2 5 4

我将交换包含5作为l的节点，以及包含7作为r的节点

交换后列表：4 7 2 5 1 8
交换后向后列出：8 1 7 4

我用多种方法测试了多次，结果要么是相同的，要么是某种无限循环引用。我想的是，当我改变下一个指针时，我已经弄乱了他们之前的指针，但是没有具体的证据。任何帮助都将不胜感激。谢谢。在

Answer 1

您可以实现将在索引处检索值的getitem方法，以及在索引处更新节点的setitem方法。这样，可以通过重新分配值来编写一个简单的swap方法：

def check_index(f):
  def wrapper(cls, _val, *args):
    if cls._next is None and _val:
      raise IndexError(f'{_val} exceeds length of deque')
    return f(cls, _val, *args)
  return wrapper

class Deque:
  def __init__(self, _val= None, _previous = None):
     self.value = _val
     self._next, self._previous = None, _previous
  @check_index
  def __getitem__(self, _index):
     return self.value if not _index else self._next[_index-1]
  @check_index
  def __setitem__(self, _index, _val):
     if not _index:
       self.value = _val
     else:
       self._next[_index-1] = _val
  def insert_val(self, _val, _trailing = None):
     if self.value is None:
        self.value = _val
     else:
        if self._next is None:
          self._next = Deque(_val, _trailing)
        else:
          self._next.insert_val(_val, self._next)
  def swap(self, _start, _finish):
    _temp = self[_start]
    self[_start] = self[_finish]
    self[_finish] = _temp
  def __str__(self):
    return f'{self.value}, {str(self._next)}' if self._next is not None else str(self.value)
  def __repr__(self):
     return f'Deque({str(self)})'

---

^{pr2}$