Leecode之反转链表

一枕眠秋雨

发布于 2024-03-11 18:03:13

740

发布于 2024-03-11 18:03:13

文章被收录于专栏：司钰秘籍司钰秘籍

一.题目及剖析

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

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

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

二.思路引入

设定三个指针,n1指向空, n2指向head,n3指向下一个元素,将n2->next指向n1,然后三个指针向后遍历重复直到n2为空,这里需要注意的是n2为空之前,n3可能已经为空,所以,我们在移动n3指针的时候要判断一下此时的n3指针是否为空,如果为空,n3精不在进行移动

三.代码引入

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *n1, *n2, *n3;
    n1 = NULL;
    n2 = n3 = head;
    if(head)
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
    }
    return n1;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-02-18，如有侵权请联系 cloudcommunity@tencent.com 删除

指针