206. 反转链表（Python）

题目

难度：★★☆☆☆
类型：链表

反转一个单链表。

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

示例

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

解答

方案1：迭代

使用迭代法反转链表需要三个临时变量：

当前结点cur：当前要处理的链表结点；

前一个结点prev：已经处理好的新链表的头结点；
临时结点tmp：用于暂存cur的下一个链表结点。
遍历链表过程中，不断进行的重复便是cur.next=prev：

prev, cur->tmp ==> prev <- cur, tmp

每一轮循环，因为有三个变量，所以需要三句话分别更新，链表方向调头工序夹在里面：

先把当前结点cur的下一个结点赋给临时结点tmp暂存；
将当前结点的连接方向调头，连接prev，cur成为新链表的头结点；
prev结点更新为新链表的头结点；
将tmp中暂存的变量归还cur结点。

class Solution(object):     # 迭代
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, prev = head, None

        while cur:
            tmp = cur.next              # 临时列表，用于暂存结果
            cur.next = prev             # 更换连接方向
            prev = cur                  # 后移
            cur = tmp                   # 后移

        return prev

方案2：递归

假设链表为：

1 -> 2 -> 3-> ... -> k-1 -> k -> k+1 -> ... -> n -> None

并且我们已经构造了函数，使得链表从k-1之后都被反转：

1 -> 2 -> 3-> ... ->k-1 -> k -> k+1 <- ... <- n

我们希望k-1的下一个结点指向k，则k.next.next=k：

1 -> 2 -> 3-> ... ->k-1 -> k <- k+1 <- ... <- n

需要注意的是，结点1的下一个结点是None，需要特殊处理，在之前操作的基础上设置k的下一个结点为None：

n -> n-1 -> ... -> k+1 \
-> k -> None
1-> 2-> 3 -> ... ->k-1 /

class Solution(object):     # 迭代
   def reverseList(self, head):
       """
       :type head: ListNode
       :rtype: ListNode
       """
       if not head or not head.next:       # 如果输入结点是空，或只有一个结点，返回即可
           return head

       p = self.reverseList(head.next)     # 将下一个结点之后的部分逆序
       head.next.next = head               # 反转当前结点
       head.next = None                    # 设置当前结点的下一个结点为None
       return p

这里，特地为大家做了一个脚本，近距离展示一下递归是如何工作的：

def create_linked_list(nums):
    """
    创建链表
    :param nums: 输入代表里链表的数字列表
    :return: 返回创建好的链表的头结点，可以得到整个链表的所有信息
    """
    if not nums:                        # 输入空列表
        return
    head = prev = ListNode(nums[0])     # 第一个结点
    for num in nums[1:]:
        tmp = ListNode(num)             # 创建当前结点
        prev.next = tmp                 # 挂在已经创建好的链表末尾
        prev = prev.next                # 指针后移
    return head


def print_linked_list(head):
    """
    打印链表
    :param head: 要打印的链表的头结点
    :return: 结点值列表
    """
    nums = []
    while head:
        nums.append(head.val)
        head = head.next
    print(nums)
    return nums


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):   
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:       # 如果输入结点是空，或只有一个结点，返回即可
            return head

        p = self.reverseList(head.next)     # 将下一个结点之后的部分逆序
        head.next.next = head               # 反转当前结点
        head.next = None                    # 设置当前结点的下一个结点为None
        print_linked_list(p)                # 展示一下处理过程，如果不需要的话可以注释掉
        return p


if __name__ == "__main__":
    head = create_linked_list([1, 2, 3, 4, 5, 6, 7, 8, 9])
    s = Solution()
    reversed_head = s.reverseList(head)

该脚本的输出为：

[9, 8]
[9, 8, 7]
[9, 8, 7, 6]
[9, 8, 7, 6, 5]
[9, 8, 7, 6, 5, 4]
[9, 8, 7, 6, 5, 4, 3]
[9, 8, 7, 6, 5, 4, 3, 2]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

创建链表（create_linked_list）和打印链表（print_linked_list）函数源自【链表基础】。

如有疑问或建议，欢迎评论区留言~

最后编辑于：2019.05.14 15:51:46