单链表_LeetCode_276.反转链表

文章目录

• 一、题目
• • 1.题目描述
  • 2.题目链接
• 二、题解报告
• • 方法一：
  • • 1.思路分析
    • 2.时间复杂度
    • 3.代码详解
  • 方法二：
  • • 1.思路分析
    • 2.时间复杂度
    • 3.代码详解

一、题目

1.题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例一： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 示例二： 输入：head = [1,2] 输出：[2,1] 示例三： 输入：head = [] 输出：[]

2.题目链接

https://leetcode.cn/problems/reverse-linked-list

二、题解报告

方法一：

1.思路分析

简单理解：比如链表为 1→2→3。创建一个新的空链表，然后用头插法依次把节点 1,2,3 插到这个新链表的头部，就得到了链表 3→2→1，这正是反转后的链表。

头插法的意思是，把一个指针 newHead 指向链表头节点，将新插入的结点插在头结点的前面，新插入的结点的指向更新为原来的头结点的地址，newHead就会指向新插入的结点，新链表的头节点为 newHead。

对于链表 1→2→3，结合代码来说，顺序为：

第一轮循环结束后，得到链表 1。 第二轮循环结束后，得到链表 2→1。 第三轮循环结束后，得到链表 3→2→1。

注：代码每轮循环结束后，newHead 表示最新得到的链表。

2.时间复杂度

 时间复杂度为O(n)。

3.代码详解

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* newHead = NULL, *cur = head;
while (cur) {
//保存下一个结点
struct ListNode* next = cur->next;
//头插
cur->next = newHead;
newHead = cur;
//再取下一个
cur = next;
}

return newHead;
}

方法二：

1.思路分析

遍历每一个结点，将每个结点的指向都调转方向。因此需要三个指针，pre初始为NULL,用来更新下一个结点（cur)的目标指向；cur是要调转方向的结点，要将cur指向之前的结点（pre），cur->next = pre;next用来更新cur，遍历下一个结点。

2.时间复杂度

 时间复杂度为O(n)。

3.代码详解

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* pre = NULL, *cur = head, *next = NULL;
while (cur) {
//保存下一个，用来更新cur
next = cur->next;
//调转指向
cur->next = pre;
pre = cur;
//更新cur
cur = next;
}
return pre;
}