【C】链表算法题2 -- 反转链表

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

 看一下题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例1：

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

示例2：

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

思路

  这道题有一个特别好但是不太容易想到的方法，那就是双指针法，之前在顺序表的算法题 -- 移除元素中曾用到过此方法，在那道题中是用两个数组的下表src和dst来遍历顺序表，从而达到去掉相同元素的效果，而在反转链表里面我们依然会用到这个方法。

  在这道题中，我们会创建3个指针n1、n2、n3，开始先让n1指向NULL，n2指向首节点，n3指向首节点的下一个节点，然后遍历原链表，每次让n2的next指针指向n1，让n3的next指针指向n2，然后让n1指向n2指向的节点，n2指向n3指向的节点，再让n3指向其next指针指向的节点，直到n2指向了NULL，最后返回n1，这样就可以达到逆置原链表的效果，画图如下：

  我们再来考虑一下特殊情况，如果按照这个逻辑，那么n3是会比n2早走到NULL的位置的，而判断循环停止的条件是以n2为不为NULL为判断条件，而如果n3为NULL的话，再让n3指向n3的next指针指向的节点，就会发生对NULL指针的解引用，会报错，所以需要判断一下n3的值，再让n3改变指向。

代码

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) 
{
    //如果链表为空，直接返回
    if (head == NULL)
    {
        return head;
    }
    //创建三个指针
    ListNode* n1, *n2, *n3;
    n1 = NULL, n2 = head, n3 = head->next;
    while (n2)
    {
        //反转链表
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

  在这道题目中，我们依然使用了双指针法来解决。双指针法是解算法题中特别重要的一个方法，该方法并不是真的只创建两个指针，而是通过创建变量来遍历并改变顺序表或者链表中的数据，这个变量可能是下标，也可能是指针。请一定要掌握双指针法这种算法思想。