leetcode 总结 09 反转链表

发表于 更新于 分类于

leetcode 09 反转链表

一道比较有意思的题，也觉得是链表里面需要掌握的一道题

给你单链表的头节点 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

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

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/linked-list/f58sg/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public:
    ListNode* reverseList(ListNode* head) {
      	//因为要返回链表，所以我们先搞一个需要返回的链表指针，初始值先置为空
        ListNode * pReturn = nullptr;
        ListNode * p = head; // 构造另外一个指针，用来标记当前移动指针的位置，也为了持有链表后续的值
        while(p != nullptr)  // 链表操作，一般就是while 语句，判空即可，一个节点一个节点的向下遍历
        {
            ListNode * tmp = p->next; // 这里需要有一个指针，持有当前操作指针的下一位，因为当前操作指针要被挪出去，后面信息需要保留
            p->next = pReturn; // 在原始长链中移除的指针，需要插入到返回链表的头结点，所以这里是插入操作。
            pReturn = p; // 原始指针更新当前指向位置，完成了返回链表的插入
            p = tmp;  // 当前工作指针就更新为工作指针的后一位，就是之前保存的原始链表的后续内容
        }
      	//最后返回我们已经逆序完成的链表
        return pReturn;

    }
};