单链表首尾交换

Question

我已经在这上面困了半天了。我可以得到一些提示或指针，如何交换一个链表的头部和尾部（而不是反转整个列表），而不复制他们的数据吗？

class myNode:

    def __init__(data, next):
         self.data = data
         self.next = next


class MyLinkedList:

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

如果我能看到代码并对它有一个解释，那就太棒了！

编辑：

null

通过列表查找列表的第二个最后节点，并将其链接到头部。

将原来的头部链接到null，就像现在一样，头部应该被交换到尾部。

Answer 1

有一些边缘情况最好单独处理，以保持代码简单。它们是大小为零、一和二的列表。

对于其中的前两个，列表根本不会改变。对于大小2，只有头部和尾部会改变，内部节点不会改变（因为没有内部节点）。

在这种情况下，左边的列表变成右边的列表(表示空指针，h/t表示头部和尾部指针）：

h    t               h    t
A -> B -> |          B -> A -> |

使用（这是伪代码而不是Python，.n指定next指针）：

                     h=A  t=B  A.n=B  B.n=|
tail.next = head     h=A  t=B  A.n=B  B.n=A
head.next = null     h=A  t=B  A.n=|  B.n=A
swap head, tail      h=B  t=A  A.n=|  B.n=A

对于所有其他情况（三个或更多节点），倒数第二个节点的指针必须更改为指向新的尾部。上面的两个节点的情况可能更容易，因为它知道头部是倒数第二个。下图显示了大小为4的情况（我已经用P标记了倒数第二个节点）：

h         p    t          h         p    t
A -> B -> C -> D -> |     D -> B -> C -> A -> |

这可以通过以下操作实现：

                          h=A  t=D  p=C A.n=B  B.n=C C.n=D  D.n=|
tail.next = head.next     h=A  t=D  p=C A.n=B  B.n=C C.n=D  D.n=B
head.next = None          h=A  t=D  p=C A.n=|  B.n=C C.n=D  D.n=B
penu.next = head          h=A  t=D  p=C A.n=|  B.n=C C.n=A  D.n=B
swap head, tail           h=D  t=A  p=C A.n=|  B.n=C C.n=A  D.n=B

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

class MyList:
    def __init__(self):
         self.head = None
         self.tail = None

    def push_back(self, data):
        if self.tail is None:
            self.head = MyNode(data)
            self.tail = self.head
        else:
            self.tail.next = MyNode(data)
            self.tail = self.tail.next

    def dump(self, desc):
        print(desc, end=' ')
        node = self.head
        while node is not None:
            print(node.data, end=' -> ')
            node = node.next
        print('|')

    def swap(self):
        # For empty and size 1, no change.

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

        # For size 2, easy swap.

        if self.head.next.next is None:
            self.tail.next = self.head
            self.head.next = None
            self.head, self.tail = self.tail, self.head
            return

        # For size 3+, little more complex, need the
        # penultimate node as well as head and tail.

        penu = self.head
        while penu.next != self.tail:
            penu = penu.next

        self.tail.next = self.head.next
        self.head.next = None
        penu.next = self.head
        self.head, self.tail = self.tail, self.head

当然，如果没有某种测试代码，什么自尊类会存在。下面将测试不同大小的列表，以便您可以看到swap操作按预期工作：

x = MyList()

# Do various sizes.

for i in range(6):
    # Add an element except for first time (so we check empty list).

    if i > 0:
        x.push_back(i)

    # Show before and after figures, making sure we restore
    # list to original state.

    x.dump('Size = %d, before:'%(i))
    x.swap()
    x.dump('Size = %d, after :'%(i))
    x.swap()
    print()

运行此代码将导致：

Size = 0, before: |
Size = 0, after : |

Size = 1, before: 1 -> |
Size = 1, after : 1 -> |

Size = 2, before: 1 -> 2 -> |
Size = 2, after : 2 -> 1 -> |

Size = 3, before: 1 -> 2 -> 3 -> |
Size = 3, after : 3 -> 2 -> 1 -> |

Size = 4, before: 1 -> 2 -> 3 -> 4 -> |
Size = 4, after : 4 -> 2 -> 3 -> 1 -> |

Size = 5, before: 1 -> 2 -> 3 -> 4 -> 5 -> |
Size = 5, after : 5 -> 2 -> 3 -> 4 -> 1 -> |

一旦您对此工作感到满意，您可能需要考虑将penu（倒数第二个节点指针）变成一个成员，就像head和tail一样，如果大小是两个或更小，则将其设置为none。这样，您就不必在每次交换节点时都进行搜索。每当调用push_back（或任何其他更改列表大小的方法）时，更新它应该比较容易。