开发者LT的博客
0%

力扣LCR024-反转链表-题解

发表于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟
原地反转单链表

题目描述

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

示例

示例 1：

img

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

示例 2：

img

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

示例 3：

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

接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) { 
        
    }
};

说明/提示

提示：

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

分析

经典的反转单链表，由于接口的head头节点实际上仅仅是头指针，没有真正的头节点。所以我们可以自己创建一个ListNode的头节点，然后借鉴头插法插入元素的思路，把从第一个节点开始往后的每个节点重新插入到头节点的next。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        //首先判断一下链表里面是否存在至少两个节点，如果不满足的话直接返回
        if(head==nullptr||head->next==nullptr)
        {
            return head;
        }
        //创建真正的头节点
        ListNode Head;
        Head.next=nullptr;
        ListNode* p=head;
        while(p!=nullptr)
        {
            //保存p的下一个节点
            ListNode* q=p->next;
            //类似头插法，把p插到head的next，作为第一个节点
            p->next=Head.next;
            Head.next=p;
            //p移动到下一位
            p=q;
        }
        return Head.next;
    }
};