C数据结构-翻转指针法、头插法实现单链表反转

前言

本文介绍以C语言实现无头单链表反转的算法：翻转指针法与头插法。

力扣试题链接

LeetCode-206.反转链表

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

一、翻转指针法

1.思路

如下图，翻转指针法的思路并不复杂，只需要改变原指针的方向即可。

关键在于如何通过迭代实现将所有结点的指针方向改变的效果。这里我们可以使用三个指针（n1、n2、n3）配合来进行翻转。

起始位置与迭代过程

创建3个指针进行翻转操作。如图为3个指针的初始化情况。n1指针指向NULL，n2指针指向原来的首结点head，而n3指针指向n2所指位置的后一个（即head->next）。设计这三个指针的思路如下：

1. 翻转指针方向至少需要两个指针。我们需要让原来指向后继结点的后继指针转而指向前驱结点，则必须有一个指针指向当前节点（即指针n2），另一个指针指向当前节点的前一个结点（即指针n1）。这样，改变后继指针所指方向只需一步：

     n2->next = n1;

 2.但在翻转完一个指针后，还需要向后遍历将所有结点之间的指针都翻转。如何向后遍历？仅仅只有两个指针，是做不到的。

3. 因此我们必须把n2原来的后继结点也保存起来，以便能向后遍历。这时我们引入了n3这个结点，它的用处就是保存n2原来的后继结点。这样，实现n2指针向后移动只需要一步：

n2 = n3;     //n2指针向后移，寻找n2后头的结点

停止条件

n2表示的是当前结点。n2初始位置为head。当n2到达原链表的最后一个结点时，链表中所有的指针都已经被翻转。因此，当n2 == NULL时，迭代停止。此时把n1看作头结点指针，n1表示的链表即反转后的链表。

循环停止的情况

特殊情况

1. 如下图，当n2刚到在最后一个结点，还没有停止循环时，n3已经指向了链表外的空NULL。这时，就不能和上面的迭代方式一样走完最后一步，因为n3 = n3->next会造成空指针访问错误。因此，只需要加一句条件判断，让最后一步不要执行该语句，即可。

2. 如果链表本身就为空，则不需要进行任何操作，仍然返回空即可。

2.代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
//翻指针方向法
struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL)
    {
        return NULL;
    }
 
    //初始条件
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    //结束条件
    while(n2)
    {
        //迭代过程
        n2->next = n1;
 
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3->next;
        }
    }
 
    return n1;
}

二、头插法

1.思路

取原来链表中的结点，头插到新链表中。

起始位置

我们仍然需考虑“如何完成头插”和“如何让指针后移”这两个问题。

cur指针仍然表示当前结点，即我们要取出并进行头插的结点，起始位置为head，即原链表的头节点。而after和翻转指针法中的n3一样，用于让cur结点后移，它始终指向cur的后一个。

newHead代表用于头插的新链表的头节点。我们将它初始化为NULL，代表此时新链表中一个结点也没有。当后续有结点插入后，NULL就成了最后一个结点的后继。

迭代过程

“取出原结点，再头插到新链表”的过程，即更改cur所指向的结点的后继的过程。因此，只需要将cur的next更改为newHead即可。

cur->next = newHead;

在头插结束后，要对各个指针所指向的位置进行调整。cur后移一个结点，after指向后移后的cur的下一个结点，newHead则要调整为新链表的头结点。代码实现如下：

1.//一趟操作的流程
 
struct ListNode* after = cur->next;
 
cur->next = newHead;    //更改cur的后继，头插入新链表
newHead = cur;    //调整newHead为新链表的头节点指针
cur = after;    //cur在原链表中后移

这个部分可以拿纸笔动手画一画，过程会更直观。

停止条件

当遍历完链表中所有的结点后，即当讲原链表中的所有节点都头插到新链表中后，循环结束。因此，当cur == NULL时，遍历完比，循环停止。此时newHead所表示的链表即反转后的链表。

特殊情况

考虑空表的情况。当head为NULL时，由于cur初始化就为head，所以cur一上来就是NULL，满足了停止条件，无法进入迭代，而直接将newHead返回。由于newHead初始化也为NULL，正好对应上，因此该代码也适用于空表的特殊情况。

2.代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
 
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;
    while(cur)
    {
        struct ListNode* after = cur->next;
 
        //头插
        cur->next = newHead;
        newHead = cur;
        cur = after;
    }
    return newHead;
}