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

简介: 本文介绍以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.但在翻转完一个指针后,还需要向后遍历将所有结点之间的指针都翻转。如何向后遍历?仅仅只有两个指针,是做不到的。



  1. 因此我们必须把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;
}


相关文章
|
1月前
|
存储 Go iOS开发
掌握Go语言:探索Go语言指针,解锁高效内存操作与动态数据结构的奥秘(19)
掌握Go语言:探索Go语言指针,解锁高效内存操作与动态数据结构的奥秘(19)
|
1月前
|
算法
【数据结构与算法】单链表反转、双链表反转(含相关题型)
【数据结构与算法】单链表反转、双链表反转(含相关题型)
30 0
|
1月前
|
存储 C语言 索引
【c语言指针详解】复杂数据结构的指针用法
【c语言指针详解】复杂数据结构的指针用法
88 0
|
8月前
【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)
【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)
29 0
|
10月前
|
算法
|
10天前
|
算法
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
数据结构和算法学习记录——习题-翻转链表(不带表头结点逆置算法、带表头结点的链表逆置算法)
8 0
|
1月前
数据结构--链表刷题(一)快慢指针(下)
数据结构--链表刷题(一)快慢指针
18 0
|
1月前
数据结构--链表刷题(一)快慢指针(上)
数据结构--链表刷题(一)快慢指针
20 0
|
1月前
|
存储 编译器 C语言
【数据结构】深入浅出理解链表中二级指针的应用
【数据结构】深入浅出理解链表中二级指针的应用
38 0
|
9月前
|
存储 算法
【数据结构】单链表面试题讲解->贰
【数据结构】单链表面试题讲解->贰