我已经在这个上面呆了半天了。我可以得到一些关于如何在不复制其数据的情况下仅交换链表的头部和尾部(而不是反转整个列表)的提示或指示吗？
class myNode:
def __init__(data, next):
self.data = data
self.next = next
class MyLinkedList:
def __init__(self):
self.head = None
self.tail = None
如果我能看到代码并对其进行解释，那就太棒了！
编辑：
基本上，我解决这个问题的最初方法是。
- 浏览列表以找到尾部(当node.next为None时停止while循环，这意味着我已经到达了末尾)
然后将尾巴连接到头部。
- 浏览列表
以找到列表的倒数第二个节点并将其链接到头部。
将原始头部链接到 null，因为现在头部应该交换到尾部。
有一些边缘情况最好单独处理，以保持代码简单。它们是大小为零、一和二的列表。
对于其中的前两个，列表根本不会改变。对于大小二，只有头部和尾部会改变，没有内部节点会改变(因为没有内部节点)。
在这种情况下，左侧的列表将变为右侧的列表(|表示空指针，h/t是头和尾指针)：
h t h t
A -> B -> | B -> A -> |
with(这是伪代码而不是 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
对于所有其他情况(三个或更多节点)，倒数第二个节点必须将其指针更改为指向新的尾部。上面的双节点情况可能更容易，因为它知道头部是倒数第二个。下图显示了大小四的情况(我用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
因此，在将其放入 Python 方面，以下程序包含方法和测试工具，因此您可以看到它的操作：
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
首先是节点类，根据 Hans 的建议修改为默认下一个指针。然后是列表类本身，根据您的原始问题进行初始化。
它还有一个push_back方法，因为如果你不能在其中放任何东西，列表就没什么用了，还有一个dump方法，这样我们就可以看到列表在每次操作后的样子。
该类的唯一另一部分是swap方法，该逻辑在本答案的前面部分已经介绍过。
当然，如果没有某种测试代码，什么自尊的类会存在。以下内容将测试不同大小的列表，以便您可以看到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(或任何其他更改列表大小的方法)时，更新它应该相对容易。
查看链接@Waffle的代码后，以下似乎是重要的类。第一个表示链表中的节点，第二个是节点的容器类，允许轻松表示空列表。目标是以就地改变表示列表的方式实现LinkedList.swap_front_back()。
class Node:
def __init__(self, value=None, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def swap_front_back(self):
"""TODO: Magic happens here"""
由于Python有一个隐式返回None，使用返回作为分解函数的一种方式，即使它被认为"不返回任何东西"也是一种安全的退出策略。因此，以下几行摆脱了最小的边缘情况：
if self.size < 2:
return
我提出的就地交换列表的策略涉及倒数第二个元素，如果它恰好是第一个元素，就会发生各种不好的事情。换句话说，不幸的是，我们必须将大小为 2 的链表作为特例(对于此实现)进行处理。
if self.size == 2:
self.head, self.tail = self.tail, self.head
self.head.next = self.tail
self.tail.next = None
return
在一般情况下，我们需要更改链表倒数第二个元素指向的位置。如果这没有发生，链表就会变成一个循环，在期望列表结束的算法中会发生各种坏事。
current = self.head
while current.next.next is not None:
current = current.next
找到倒数第二个元素后，我们就可以进行实际的指针操作。
current.next.next = self.head.next
# Now the former last element points to the second element
# A->B->C->D->B
current.next = self.head
# Now the second-to-last element points to the previous head
# A->B->C->A D->B
self.head.next = None
# We don't want circles, so we eliminate A being first and last
# D->B->C->A
self.head, self.tail = self.tail, self.head
# Even after the internal manipulations are done, the
# LinkedList needs to be updated to reference the appropriate
# locations.
综上所述，我们可以创建所需的方法：
def swap_front_back(self):
if self.size < 2:
return
if self.size == 2:
self.head, self.tail = self.tail, self.head
self.head.next = self.tail
self.tail.next = None
return
current = self.head
while current.next.next is not None:
current = current.next
self.tail.next = self.head.next
current.next = self.head
self.head.next = None
self.head, self.tail= self.tail, self.head
如果 LinkedList 太小以至于不需要发生交换，它会提前返回，它将转置作为特殊情况处理，否则它首先找到倒数第二个节点，然后使用它来调整必要的指针。
通常，交换依赖于第三个变量来存储要反转的值之一。例如，给定列表[3, 4, 1, 6, 5]，交换第一个和最后一个可以像这样完成：
l = [3, 4, 1, 6, 5]
_temp = l[0] #first value
l[0] = l[-1]
l[-1] = _temp
#[5, 4, 1, 6, 3]
下面的实现使用默认参数，该参数将存储对列表中第一个节点的引用。到达列表末尾后，将进行类似于上述交换的简单交换操作：
class LinkedList:
def __init__(self, head=None):
self.head = head
self._next = None
def insert_node(self, val):
if self.head is None:
self.head = val
else:
getattr(self._next, 'insert_node', lambda x:setattr(self, '_next', LinkedList(x)))(val)
def swap(self, first = None, count = 0):
if not self._next and self.head is not None:
_head = getattr(self, 'head')
if first:
self.head = getattr(first, 'head')
setattr(first, 'head', _head)
else:
if self.head:
self._next.swap(first = self if not count else first, count = 1)
@classmethod
def load_list(cls, length = 5):
_l = cls()
import random
for _ in range(length):
_l.insert_node(random.randint(1, 100))
return _l
def flatten(self):
if self.head is not None:
return [self.head, *getattr(self._next, 'flatten', lambda :'')()]
return ''
def __repr__(self):
return ', '.join(map(str, self.flatten()))
这个简单的递归适用于任何大小的列表：
for i in range(10):
l = LinkedList.load_list(length = i)
_s = repr(l)
l.swap()
print(f'{_s} -> {repr(l)}')
输出：
->
14 -> 14
80, 57 -> 57, 80
83, 44, 80 -> 80, 44, 83
94, 10, 42, 81 -> 81, 10, 42, 94
25, 26, 32, 31, 55 -> 55, 26, 32, 31, 25
8, 25, 25, 84, 83, 49 -> 49, 25, 25, 84, 83, 8
19, 95, 3, 33, 4, 56, 33 -> 33, 95, 3, 33, 4, 56, 19
97, 92, 37, 100, 27, 24, 33, 17 -> 17, 92, 37, 100, 27, 24, 33, 97
72, 24, 56, 18, 9, 64, 82, 85, 97 -> 97, 24, 56, 18, 9, 64, 82, 85, 72
最初假设你有 A -> B -> C -> D-> 无 头：A 尾：D
你想要 D -> B -> C -> A-> 无 头：D，尾：A
var next = self.head.next
var temp = self.head
self.head = self.tail
self.tail = temp
self.head.next = next
self.tail.next = None