学长冷月带你怒刷LeetCode之反转链表

01

—

前言

链表的操作是数据结构中最基础的算法之一，反转列表也是一道经典的笔试题。很多公司的面试题库中都有这道题，有的公司明确题目要求不能使用额外的节点存储空间，有的没有明确说明，但是如果面试者使用了额外的节点存储空间做中转，会得到一个比较低的分数。本题选自leetcode的206题，感兴趣的小伙伴可以去练习一下。206.反转链表

02

—

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

03

—

冷月题解

因为是操作单链表，而单链表是单向指向的，如果要求空间复杂度为O(1)的情况下，我们只能使用迭代的方式。需要新增加两个指针。冷月把完整实例代码放在博客上了，大家可以进入查看学长冷月带你怒刷LeetCode之反转链表

struct ListNode * cur = head; //指向当前节点

struct ListNode * pre = NULL; //指向上一个节点

一开始，我们链表是如下的形式：

此时head不为空，我们进入第一次循环。

head = head -> next; //指向下一个结点

cur->next = pre; //当前节点 指向 上一个节点

如下图所示：

这时，我们已经将第一个节点指向了pre,也就是说将第一个节点反转了过来，下一步我们要将pre和cur移动一下位置，方便下一次循环。

pre = cur; //指针域往后挪动cur = head; //指针域往后挪动

如下图所示：

这时已经完成了第一次循环的所有步骤，我们成功将第一个节点反转，并且从第二个节点开始成为了新的表头，大家可以与第一张图片对比一下，是不是很相似呢？然后进入第二次循环，循环的步骤方法和第一次的一模一样，第二次循环完后的图示如下：

再经过四次循环后，cur = head = NULL，将会跳出循环，我们只需要将pre 返回出去即可，获得反转后的链表。图示如下：

完整代码如下：

/**
公众号：学长冷月
**/
struct ListNode* reverseList(struct ListNode* head){
     struct ListNode * cur = head;  //指向当前节点
     struct ListNode * pre = NULL; //指向上一个节点

    while(head){ //如果链表不为空则进入循环
        head = head -> next; //指向下一个结点
        cur->next = pre; //当前节点 指向 上一个节点
        pre = cur; //指针域往后挪动
        cur = head; //指针域往后挪动
    }
    return pre;
}

03

—

总结一下

这道反转链表的题属于很基础的入门题，是每位小伙伴都应该掌握的难度。光说不练假把式，大家要先理解，然后将代码自己实现一下才能将知识转变成自己的。