问题描述

反转一个单链表。

示例:

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

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解决方案

1.迭代法

def reverse_loop(head):    """    循坏迭代    :param head:    :return:    """    if not head or not head.next:        return head    pre = None    while head:        next = head.next    # 缓存当前节点的向后指针，待下次迭代用        head.next = pre     # 这一步是反转的关键，相当于把当前的向前指针作为当前节点的向后指针        pre = head          # 作为下次迭代时的（当前节点的）向前指针        head = next         # 作为下次迭代时的（当前）节点    return pre              # 返回头指针，头指针就是迭代到最后一次时的head变量（赋值给了pre）

2.递归法

def reverse_recursion(head):    """    递归法    基准条件是将前置节点的下一位替换成自己，并将自己的下一个节点置空    :param head:    :return:    """    if not head or not head.next:                   # 处理边界情况        return head    new_head = reverse_recursion(head.next)    head.next.next = head    head.next = None    return new_head