单链表反转两种方法

╰半夏微凉° 2022-09-09 09:24 99阅读 0赞

最近同学介绍了一个lettcode(力扣)OJ给我，个人认为这个网站比母校的oj，杭电oj界面友好很多，题库充足，且支持多种主流语言，很适合闲时刷刷提高算法能力，算法的练习如同内功的修炼，碰到算法问题，经常有一种无力感，只能慢慢总结了。

链表是一种重要的数据结构，因为有递归性质，所以总是难以理解，涉及链表的复杂操作总是感觉一头雾水，看别人的实现代码总是似懂非懂，看完就忘，实际上就是没有理解透彻，特意花了一天时间重新学习了单链表的常见操作-单链表反转，理解和总结两种实现方法。

首先要了解一个链表节点的数据结构：  
![在这里插入图片描述][20190129202114436.png]  
value代表该节点存储的值，next指向下一个节点，next可能指向一个单一节点，也可能指向一个链表，也可能指向null(代表尾节点)。  
**方法一：头节点插入法**  
**实现步骤：**

1.  创建一个带头节点的链表resultList
2.  定义一个循环链表变量p，p的初始值为待反转的链表
3.  遍历待反转的链表，遍历条件为 (p !=null)  
    3.1 定义一个临时链表变量tempList保存p->next的值（因为p->next值会改变），用于下一次循环。  
    3.2 把p当前指向的首节点和resultList链表的头节点之后的节点拼接起来。  
    3.3 把3.2步骤中拼接的节点 再拼接到resultList头节点后。  
    3.4 p重新赋值为3.1步骤中保存的tempList的值。
4.  返回resultList->next.即反转后的链表。

**图解：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyeGlhb2xvbmcxMjM_size_16_color_FFFFFF_t_70]  
图1就是待反转的原始链表，图2是 带头节点的链表resultList。  
可以看到p是一个循环变量，初始值指向待反转的原始链表。  
通过p变量遍历链表，在遍历中（列举的值为第一次循环的情况）：

*  定义一个临时链表变量tempList保存p->next的值，tempList指向图1.2
 *  把p当前指向的首节点(图1.1)和resultList链表的头节点之后的节点（图2.2）拼接起来。
 *  把3.2步骤中拼接的节点(图3.2) 再拼接到resultList头节点后。
 *  p重新赋值为3.1步骤中保存的tempList的值，即图1.2。

最后返回resultList->next，也就是去除了头节点-1的值。

通过头结点插入法实现链表反转功能，主要难点就是在循环中的3.2和3.3步骤的理解。  
需要注意的是，就是关注循环变量p的值，也就是指向的变化，传统的遍历过程就是条件为p!=null,处理,p=p->next。但是在这个头结点插入代码中，p->next的值发生的变化，因为要将resultList结果链表的内容拼接到p的首节点后，所以要定义一个临时变量存p->next。

**方法二：就地反转**  
头结点插入法的实质是重新创建了一个新的链表，通过遍历待反转链表，将链表每一个节点插入到创建的链表中，然后的到的这个创建的链表就是反转后的链表。而就地反转实质就是在待反转链表基础上修改节点顺序得到反转链表。所以原理还是不同的。

**图解：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyeGlhb2xvbmcxMjM_size_16_color_FFFFFF_t_70 1]  
个人认为就地反转比头结点插入稍微难理解一点。  
宏观上来看，要实现节点1和节点2反转，需要将节点1插入节点2和节点3当中，然后将头节点为2的链表插入结果链表头结点后面，然后再后移一个节点做同样的操作。  
然而涉及到两个节点的循环赋值，这个操作顺序就比较重要了。  
正确的步骤是先将节点2切分出来，再将节点2插入-1和1之间。

**实现步骤**

1.  创建一个带头节点的链表resultList，头结点指向待反转的链表。
2.  创建p、pNext两个用于循环操作，分别指向两个待反转节点的位置,初始值如图所示，指向1和2
3.  遍历带反转的链表，循环条件是pNext!=null.  
    3.1 从链表中分割出pNext节点，也就是让p指向pNext->next。  
    3.2 让pNext指向经过3.1操作之后的resultList.next（1->3->4->5）  
    3.3 让resultList头结点指向pNext(2->1->3->4->5)  
    3.4 让pNext指向p的下一个节点  
    难点在于理解循环中resultList.next指向性的变化，以及p和pNext两个变量的变化，p指向的链表首结点永远是1,只是节点1在resultList链表中位置在发生变化，而pNext是随着p移动的，脑子中间可以有一个摆绳模型，在起始点位置发力，绳子的高点位置会移到绳尾，那个最高点就是p变量位置。

**代码实现：**  
头结点插入：

public static ListNode reverseListByInsert(ListNode listNode){
            //定义一个带头节点的
            ListNode resultList = new ListNode(-1);
            //循环节点
            ListNode p = listNode;
            while(p!= null){
                //保存插入点之后的数据
                ListNode tempList = p.next;
                p.next = resultList.next;
                resultList.next = p;
                p = tempList;
            }
            return resultList.next;
        }

就地反转:

public static ListNode reverseListByLocal(ListNode listNode){
            ListNode resultList = new ListNode(-1);
            resultList.next= listNode;
            ListNode p = listNode;
            ListNode pNext = p.next;
            while (pNext!=null){
                p.next = pNext.next;
                pNext.next = resultList.next;
                resultList.next = pNext;
                pNext=p.next;
            }
            return resultList.next;
        }

单链表的操作困扰了很多年，或许还将困扰下去，但是至少有了更加深入的认识。这部分内容确实相对有点难以理解。推荐的学习方法就是先看别人代码，再画图了解代码的每一个过程，再根据画的图独立写代码实现，然后再调试debug，查看变量变化情况，再找类似练习题,多想多练。（就地反转的方法还需要细讲）。

[20190129202114436.png]: /images/20220829/e347cd8178e945baa4ef89aa49d0b2bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyeGlhb2xvbmcxMjM_size_16_color_FFFFFF_t_70]: /images/20220829/a0e4d8f744f342e693422aec254bd29f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N1cGVyeGlhb2xvbmcxMjM_size_16_color_FFFFFF_t_70 1]: /images/20220829/5d9b95fe23914c3b9e5d1e5b64202371.png