题目链接

反转链表

题目描述

给定一个单链表的头结点 head，请反转该链表，并返回新链表的表头。

数据范围: 链表长度满足 。 要求: 空间复杂度 ，时间复杂度 。

示例: 输入: {1,2,3}

输出: {3,2,1}

解题思路

反转链表的核心思想是逐个改变节点的 next 指针方向。我们可以使用迭代的方法，通过三个指针来高效地完成这个任务，这通常被称为"头插法"的变体或迭代反转。

算法步骤 (迭代法):

  1. 定义三个指针：

    • prev：指向反转后链表的头节点，初始为 nullptr (或 null)。它代表当前节点 curr 的新 next 应该指向哪里。
    • curr：指向当前正在处理的节点，初始为 head。
    • nextTemp：临时保存 curr 节点的下一个节点，以防断链。

  2. 循环遍历原链表，当 curr 不为空时： a. 首先，用 nextTemp 保存 curr 的下一个节点：nextTemp = curr->next。这是为了在我们修改 curr->next 指针后，还能找到原链表的下一个节点。 b. 然后，执行反转操作：将 curr 的 next 指针指向 prev。curr->next = prev。 c. 移动指针为下一次迭代做准备： - prev 更新为 curr，因为 curr 已经成为反转后链表的新的头部。 - curr 更新为 nextTemp，移动到原链表的下一个节点。

  3. 循环结束后，curr 会变为 nullptr，而 prev 将指向原链表的最后一个节点，也就是新链表的头节点。返回 prev 即可。

这个过程就像是将原链表的节点一个一个地"摘下来"，然后"倒着"插入到 prev 指针所维护的新链表中。

代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* ReverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next; // 临时保存下一个节点
            curr->next = prev;              // 反转指针
            prev = curr;                    // prev 前进
            curr = nextTemp;                // curr 前进
        }
        
        return prev; // 返回新的头节点
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next; // 临时保存下一个节点
            curr.next = prev;             // 反转指针
            prev = curr;                  // prev 前进
            curr = nextTemp;              // curr 前进
        }
        
        return prev; // 返回新的头节点
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def ReverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            next_temp = curr.next  # 临时保存下一个节点
            curr.next = prev       # 反转指针
            prev = curr            # prev 前进
            curr = next_temp       # curr 前进
            
        return prev # 返回新的头节点

算法及复杂度

  • 算法: 迭代 (双指针/三指针)
  • 时间复杂度: ，其中 是链表的节点数。我们对链表进行了一次完整的遍历。
  • 空间复杂度: 。我们只使用了常数个额外的指针变量，满足题目要求。