206. 反转链表

206. 反转链表

方法 1：递归

思路

递归获取子链表的反转之后的头节点，然后将当前层的两个节点反转即可。

代码

1
2
3
4
5
6
7
8
9
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
	    # 使 head.next 以及 head.next.next 有效
        if not head or not head.next:
            return head
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return head

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。递归过程中的栈空间的使用。

方法 2：迭代

思路

用双指针 cur 和 pre 一边走一边转换即可，cur 走到 None 的时候，pre 就走到最后一个节点了，返回即可。

代码

1
2
3
4
5
6
7
8
9
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, pre = head, None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

复杂度

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。