LeetCode 206 链表反转

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

方法一 迭代法

思路

1. 创建一个新的头节点 new_head
2. 在整个遍历的过程中，一共涉及到三个节点，新的头节点，原链表中的头节点以及头节点的下一个节点。
3. 首先要将头节点的下一个节点保存起来，这样在原头节点反转到新头节点的时候，不会使链表断掉
4. 然后，进行反转，将原头节点的next指向新头节点
5. 最后，移动指针，再重复上述操作，即遍历链表
6. 时间复杂度：O(n)
   空间复杂度：O(1)

代码

class Solution(object):
    def reverseList(self, root):
        new_head = None
        head = root
        while head:
            nxt = head.next
            head.next = new_head
            new_head = head
            head = nxt
        return new_head

方法二 递归

思路

1. 这种方法相当于从后往前遍历
2. 让新旧头节点先移动在链表的最后，然后反转链表

代码

    def reverseList(self, head):
        if  head== None or head.next == None:
            return head
        root = self.reverseList(head.next) # 将头节点移动到最后，然后从后往前遍历
        head.next.next = head  # 反转链表
        head.next = None  # 打破原链表中当前节点与下一个的关系， 使其变成相当于链表中的最后一个节点，可以看做初始化。
        return root

参考： https://blog.csdn.net/FX677588/article/details/72357389