反转链表

1->2->3->4->5->NULL

5->4->3->2->1->NULL

迭代法

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        cur = head
        while cur:
            a = cur.next
            cur.next = prev
            prev = cur
            cur = a
        return prev

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var  prev *ListNode
    cur := head
    for {
        if cur == nil {
            break
        }
        // 获取指向当前的下一个
        a := cur.Next
        // 当前的指向前一个
        cur.Next = prev
        // 为下次循环准备，前一个变成当前的
        prev = cur
        // 当前的变成下一个
        cur = a
    }
    return prev
}

时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。

递归

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def handle(cur, prev):
            # 终止条件
            if not cur:
                return prev
            # 递归执行
            res = handle(cur.next, cur)
            # 重复逻辑，将指针指向前一个，前后逻辑不影响
            cur.next = prev
            return res
        return handle(head, None)

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    # 判断结束条件，当前节点为空，或者该节点的指向为空
    if head == nil || head.Next == nil {
        return head
    }
    # 递归调用，直接拿到最后一个的前一个节点
    node := reverseList(head.Next)
    # 然后最后一个前一个节点的next，也就是最后一个节点，最后一个节点的next指针指向他前一个节点
    head.Next.Next = head
    # 修改当前指向nil
    head.Next = nil
    return node
}

不要人肉递归，当前指向nil了，前一个怎么办，通用就是前一个指向nil
要在递归后再修改指向，不然就找不到最后一层，无法进行递归