目录

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上测算代码的时间复杂度和空间复杂度均为

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;
}

时间复杂度为,空间复杂度为

思想:只需要反过来指即可

执行步骤

1.保存下一节点的指针

 struct ListNode* next = curr->next;

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

curr->next = prev;

3.移动快慢指针

        prev = curr;
        curr = next;