当前位置：首页 > news >正文

L2.【LeetCode笔记】反转链表

news 2024/11/2 1:13:07

1.题目

2.自解

代码

提交结果

3.代码分析

4.LeetCode官方解法

代码

执行步骤

1.保存下一节点的指针

2.拆除原先的指针,设置节点的新指针

3.移动快慢指针

1.题目

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

2.自解

代码

为了练习87.【C语言】数据结构之链表的头插和尾插讲过的头插函数,另外开辟空间,使用遍历算法

struct ListNode* reverseList(struct ListNode* head) 
{typedef struct c_ListNode{int c_val;struct ListNode* c_next;}c_L;c_L* c_head=NULL;struct ListNode* cur=head;while (cur){int x=cur->val;{c_L* newnode = (c_L*)malloc(sizeof(c_L));newnode->c_val = x;newnode->c_next = NULL;newnode->c_next = c_head;c_head = newnode;}cur=cur->next;}return c_head;
}

提交结果

LeetCode上测算代码的时间复杂度和空间复杂度均为 $O(N)$

3.代码分析

1.反转链表显然使用头插,但不能在原来链表的基础上头插,数据会被覆盖,因此本代码创建了初始化了一个新链表struct c_ListNode(为copy_ListNode的缩写,复制ListNode的结构),成员变量为c_val(copy_val的缩写)和c_next(c_next的缩写)

    typedef struct c_ListNode{int c_val;struct ListNode* c_next;}c_L;

2.c_L链表的头指针初始化为NULL，cur为ListNode的head头节点的拷贝

c_L* c_head=NULL;
struct ListNode* cur=head;

3.while (cur)未到NULL则继续遍历ListNode链表,x取得当前cur指向的节点的val,c_L* newnode = (c_L*)malloc(sizeof(c_L));为新节点newnode开辟空间,newnode->c_val = x;和newnode->c_next = NULL;初始化化新节点

    while (cur){int x=cur->val;{c_L* newnode = (c_L*)malloc(sizeof(c_L));newnode->c_val = x;newnode->c_next = NULL;newnode->c_next = c_head;c_head = newnode;}cur=cur->next;}

4.LeetCode官方解法

代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) 
{//双指针struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}

时间复杂度为 $O(N)$ ,空间复杂度为 $O(1)$