【leetcode天梯】链表 · 206 反转链表

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

题目链接：

206. 反转链表 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-linked-list/

---

解题思路：

傻瓜法1：创建一个新链表挨个遍历

这种操作应该是最容易想到的，但是也是复杂度最高的。我们需要有一个指针从后往前挨个遍历，但是单链表是没办法从后往前遍历的，因此我们需要令一个指针从前向后遍历到最后一个，然后将该结点插入新链表；然后再从前向后遍历到倒数第二个，再将其插入单链表····这样的操作的时间复杂度应当为：

即，这种算法的时间复杂度将达到，是非常不理想的，因此这种方法，我们直接淘汰！

常规法2：使用三个指针翻转

接下来我们想到的就是直接对原链表进行操作，将箭头从前向后挨个翻转不就完了？我们不需要去将数字翻转，而是尝试将结点之间的箭头进行翻转！

这时我们就要用到三个指针进行翻转操作，其逻辑思路是用指针n1作为新链表的表头；指针n2用来更改其指向结点的next，使原链表结点与n1相连；指针n3则用来给保留n2走下一步的结点地址，其主要逻辑操作如下：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    if(head==NULL)
    return NULL; //若为空链表，直接输出NULL
    while(n2) //n2为空，说明n2遍历完链表了
    {
        struct ListNode* n3=n2->next; //n3指向原链表的第一个结点之后（可能为NULL）
        n2->next=n1; //将n2当前指向的结点的next指向n1
        n1=n2; //将新链表的表头指针n1更新
        n2=n3; //n2继续向后走一步
    }
    return n1;
}

 

总结一下：这道题使用三指针来操作的做法中规中矩，一个指针用来充当新链表的表头指针，一个指针用来遍历当前链表，另一个用来保存当前结点的下一个结点位置。

常规法3：将链表元素进行头插

这种操作也是非常聪明的，我们使用一个指针从前向后挨个遍历，另一个指针对每个结点进行头插操作，第三个指针用来保留下一个结点的地址，这样就自然使得原单链表进行逆置了。

 

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* newHead=NULL;
    struct ListNode* cur=head;
    while(cur) //当cur为空时，说明cur已经遍历完链表了
    {
        struct ListNode* next=cur->next; //cur每往后走一步，都设置一个next保存cur的下一步位置
        cur->next=newHead; //将cur指向新链表的第一个结点(可能为NULL)
        newHead=cur; //将链表的头指针指向cur
        cur=next; //cur向后走一步
    }
    return newHead;
}

总结一下：灵活使用我们在初学单链表时的一些基本操作，是我们想每一道链表题的第一步，关于链表的一些题目讲到本质来说，不过就是将“增删改查”的操作复合起来罢了。