剑指offer-24

剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

解法

头插法

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        newHead = ListNode()

        cur = head
        while cur:
            
            
            temp = ListNode(cur.val)
            temp.next = newHead.next
            newHead.next = temp
            cur = cur.next

        return newHead.next

反转链表 - 反转链表 - 力扣（LeetCode） (leetcode-cn.com)

迭代

假设链表为 $1 \rightarrow 2 \rightarrow 3 \rightarrow \varnothing$ ，$\varnothing \leftarrow 1 \leftarrow 2 \leftarrow 3$。

在遍历链表时，将当前节点的 $next$ 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须存储其前一个节点。

在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            next = curr.next # 保存后一节点
            curr.next = prev # 指向前一个节点
            prev = curr  # 指向当前节点
            curr = next # 遍历下一个节点
        
        return prev
            

递归

递归版本稍微复杂一些，其关键在于反向工作。假设链表的其余部分已经被反转，现在应该如何反转它前面的部分？

假设链表为：
$$
n _ { 1 } \rightarrow \ldots \rightarrow n k - 1 \rightarrow n k \rightarrow n k + 1 \rightarrow \ldots \rightarrow n m \rightarrow \varnothing
$$
若从节点$n_{k+1}$到$n_m$已经被反转，而我们正处于$n_k$。
$$
n _ { 1 } \rightarrow \ldots \rightarrow n _ { k - 1 } \rightarrow n k \rightarrow n k + 1 \leftarrow \ldots \leftarrow n _ { m }
$$
我们希望 $n_{k+1}$ 的下一个节点指向$n_k$。

所以，$n_k.next.next=n_k$。

需要注意的是 $n_1$的下一个节点必须指向 $\varnothing$ 。如果忽略了这一点，链表中可能会产生环。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        newHead = self.reverseList(head.next) # 转置下一个节点
        head.next.next =head
        head.next = None
        return newHead