交换双向链表中的节点

Question

我正在尝试使用 python 交换双向链表中的两个节点。它在一些测试用例中工作，但在少数测试用例中没有给出正确的输出。

输入格式：

第一行包含一个整数，表示测试用例的数量。

每个测试用例有4行。第一行包含列表中的元素数，第二行包含由 space.

分隔的列表元素

第三行和第四行包含要交换的节点号 X 和 Y。

示例输入

2

6

1 2 3 4 5 6

1

5

6

1 2 3 4 5 6

1

6

输出： 第一个测试用例的输出应该是 5 2 3 4 1 6 ，但我只在输出中得到 1 6 。第二个测试用例的输出应该是 6 2 3 4 5 1 但我得到的输出只有 1。

下面的代码片段：

# Don't change this
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

def insertEnd(head, data):
  if head is None:
    new_node = Node(data);
    head = new_node;
    return head;
  n = head;
  while n.next is not None:
    n = n.next;
  new_node = Node(data);
  n.next = new_node;
  new_node.prev = n;
  return head;

def printList(node):
  while (node != None):
    print(node.data, end=' ');
    node = node.next;
  print();



# Enter your code here
def swapNodes(head,X,Y):

  if head is None or head.next is None:
    return

  if X == Y:
    return head

  def countLength(head):
    current = head
    count = 1
    while current.next is not None:
      count += 1
      current = current.next
    return count

  size = countLength(head)

  if X > size or Y > size:
    return head

  current = head
  node1 = None
  while (current != None and current.data != X):
    current = current.next
  node1 = current

  current = head
  node2 = None
  while (current != None and current.data != Y):
    current = current.next
  node2 = current

  if node1.prev == None:
    head = node2
  elif node2.prev == None:
    head = node1

  temp = node1.next
  node1.next = node2.next
  node2.next = temp

  if node1.next != None:
    node1.next.prev = node1
  if node2.next != None:
    node2.next.prev = node2

  temp = node1.prev
  node1.prev = node2.prev
  node2.prev = temp

  if node1.prev != None:
    node1.prev.next = node1
  if node2.prev != None:
    node2.prev.next = node2
  return head


# Don't edit this
if __name__ == "__main__":
    T = int(input());
    for i in range(T):
        N = int(input());
        head = None;
        if(N!=0):
            inp = input().strip().split();
        for j in inp:
            head = insertEnd(head,int(j.strip()));
        X = int(input().strip());
        Y = int(input().strip());
        swapNodes(head,X,Y);
        printList(head);

Answer 1

模板代码似乎表明 swapNodes 不应该 return 任何东西，并且 head 不应该改变。这是因为在驱动程序代码中我们只有这个：

swapNodes(head,X,Y);

显然可以交换列表中的第一个值，我们必须得出结论，本练习不是寻找移动整个节点的解决方案，而只是移动值。否则就无法移动头节点。

如果驱动程序代码看起来像这样，您的实现就会成功：

head = swapNodes(head,X,Y);

但我假设代码不应该被修改。

所以...只需重写您的方法，并使其交换两个已识别节点中的 data，这实际上会使工作变得容易得多 - 正如您所理解的那样。

交换双向链表中的节点

Swap nodes in doubly linked list

python-3.x

doubly-linked-list