数据结构-链表反转

题目：

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

这道题目可以用迭代，递归两种方法来实现

迭代

假设存在链表 1 → 2 → 3 → 4 → 5 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3 ← 4 ← 5。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。

在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

根据题目总结一下核心的操作逻辑：

从头节点 1 开始，1 指向 2，更改指向顺序，需要将 2 的指针指向 1 (此时，虽然 2 的指针方向已经指向 1，但是 1 的指针方向没有改变，依然指向 2，则是 2 → 1 → 2 → 1….. ), 同时也要存储 2 的下一个节点 3，以便接下来迭代操作 2 和 3 节点之间的指针反转，每两个相邻节点进行相同的操作。迭代最后，尾节点 5 无后续节点，则跳出迭代。

在迭代完相邻节点的指针反转后，还需要做的两步

1. 原头节点指向 None，变成尾节点

2. 将原尾节点设置成新的头节点

操作完成～～！！

def reversed_self(self):
    """翻转链表自身."""
    if self.head is None or self.head.next_node is None:
        return

    pre = self.head
    node = self.head.next_node

    while node is not None:

        pre,node = self.__reversed_with_two_node(pre,node)
        """循环到最后一位 node is None退出"""

    """将原链表的头节点指向为下一节点 改为 指向为None"""
    self.head.next_node = None
    """将头节点设置为原链表的尾节点,链表反转则成功。链表元素位置不变，但是元素之间的指向改变"""
    self.head = pre


def __reversed_with_two_node(self, pre, node):
    """翻转相邻两个节点.
    参数:
        pre:前一个节点
        node:当前节点
    返回:
        *******(pre,node):下一个相邻节点的元组
    """

    tmp = node.next_node
    node.next_node = pre

    pre = node
    node = tmp
    return pre, node

调试图：

while node is not None:

    pre,node = self.__reversed_with_two_node(pre,node)

核心步骤迭代完，链表中的节点指向已经反转

上图。此时，节点之间指针反转完毕，虽然指针反转了，但是头节点还是 1 ， 因为 1 指向仍然为 2 还没有处理。并且 5 还不是头节点，

对应的还没有执行

self.head.next_node = None
self.head = pre

操作完下面两步后，上图中，1 的下一个节点指针变成None， 头节点赋值为 5

self.head.next_node = None
self.head = pre