题解 | #反转链表#

题目的主要信息：

• 给定一个长度为$nn$的链表，反转该链表，输出表头

举一反三：

学习完本题的思路你可以解决如下题目：

JZ6. 从尾到头打印链表

方法一：迭代（推荐使用）

思路：

将链表反转，就是将每个表元的指针从向后变成向前，那我们可以遍历原始链表，将遇到的节点一一指针逆向即可。指针怎么逆向？不过就是断掉当前节点向后的指针，改为向前罢了。

cur.next = pre

具体做法：

• step 1：优先处理空链表，空链表不需要反转。
• step 2：我们可以设置两个指针，一个当前节点的指针，一个上一个节点的指针（初始为空）。
• step 3：遍历整个链表，每到一个节点，断开当前节点与后面节点的指针，并用临时变量记录后一个节点，然后当前节点指向上一个节点，即可以将指针逆向。
• step 4：再轮换当前指针与上一个指针，让它们进入下一个节点及下一个节点的前序节点。

图示：

Java实现代码：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //处理空链表
        if(head == null) 
            return null;
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            //断开链表，要记录后续一个
            ListNode temp = cur.next; 
            //当前的next指向前一个
            cur.next = pre; 
            //前一个更新为当前
            pre = cur; 
            //当前更新为刚刚记录的后一个
            cur = temp; 
        }
        return pre;
    }
}

C++实现代码：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //处理空链表
        if(pHead == NULL)
            return NULL;
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        while(cur != NULL){
            //断开链表，要记录后续一个
            ListNode* temp = cur->next; 
            //当前的next指向前一个
            cur->next = pre; 
            //前一个更新为当前
            pre = cur; 
            //当前更新为刚刚记录的后一个
            cur = temp; 
        }
        return pre;
    }
};

Python实现代码：

class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        #处理空链表
        if not head:
            return None
        cur = head
        pre = None
        while cur:
            #断开链表，要记录后续一个
            temp = cur.next 
            #当前的next指向前一个
            cur.next = pre
            #前一个更新为当前
            pre = cur 
            #当前更新为刚刚记录的后一个
            cur = temp
        return pre

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历链表一次，一次循环
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间使用

方法二：递归（扩展思路）

思路：

从上述方法一，我们可以看到每当我们反转链表的一个节点以后，要遍历进入下一个节点进入反转，相当于对后续的子链表进行反转，这可以看成是一个子问题，因此我们也可以使用递归，其三段式模版为：

• 终止条件： 当到达链表尾，要么当前指针是空，要么下一个指针是空，就返回。
• 返回值： 每一级返回反转后的子问题的头节点。
• 本级任务： 先进入后一个节点作为子问题。等到子问题都反转完成，再将本级节点与后一个的指针反转。

具体做法：

• step 1：对于每个节点我们递归向下遍历到最后的尾节点。
• step 2：然后往上依次逆转两个节点。
• step 3：将逆转后的本层节点，即反转后这后半段子链表的尾，指向null，返回最底层上来的头部节点。

Java实现代码：

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //递归结束条件
        if(head == null || head.next == null)
            return head;
        //反转下一个
        ListNode newHead = ReverseList(head.next); 
        //逆转本级节点
        head.next.next = head; 
        //尾部设置空节点
        head.next = null; 
        return newHead;
    }
}

C++实现代码：

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        //递归结束条件
        if(pHead == NULL || pHead->next == NULL)
            return pHead;
        //反转下一个
        ListNode* newHead = ReverseList(pHead->next);
        //逆转本级节点
        pHead->next->next = pHead; 
        //尾部设置空节点
        pHead->next = NULL; 
        return newHead;
    }
};

Python实现代码：

import sys
#设置递归深度
sys.setrecursionlimit(100000) 
class Solution:
    def ReverseList(self , head: ListNode) -> ListNode:
        #递归结束条件
        if head is None or head.next is None:
            return head
        #反转下一个
        newHead = self.ReverseList(head.next)
        #逆转本级节点
        head.next.next = head 
        #尾部设置空节点
        head.next = None
        return newHead

复杂度分析：

• 时间复杂度：$O(n)O(n)$，相当于递归遍历一次链表
• 空间复杂度：$O(n)O(n)$，递归栈深度为链表长度$nn$