LeetCode 0206. 反转链表

【LetMeFly】206.反转链表

力扣题目链接：https://leetcode.cn/problems/reverse-linked-list/

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

 

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

 

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

方法一：遍历过程中，记录上一个节点

要把链表翻转，也就是把本应该指向下一个节点的指针指向上一个节点。

我们只需要遍历一遍链表，并记录下链表的上一个节点（初始值为null）

这样，在遍历过程中，我们先记录下下一个节点是什么，将这个节点的next指向上一个节点，并更新当前节点和上一个节点，直到遍历到节点尾部即可。

• 时间复杂度$O(n)$，其中$n$是链表长度
• 空间复杂度$O(1)$

AC代码

C++

// From 2022-08-21 10:33:03 To 2022-08-21 10:34:04
// 1min 码完
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* lastNode = nullptr;
        while (head) {
            ListNode* nextNode = head->next;
            head->next = lastNode;
            lastNode = head;
            head = nextNode;
        }
        return lastNode;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126448252