【力扣】【面试：单链表2】反转链表【剑指 Offer II 024. 反转链表】_力扣的024反转链表

问题链接：

力扣

---

问题描述：

剑指 Offer II 024. 反转链表

难度简单34

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

---

问题分析：

直奔题目要求：

示例 3：

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

//需要注意是存在空链表的
 

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

---

解决方案：

分析题目我们不拿发现，面试中如果使用构建新链表来进行反转的话，感谢信一封直接拿下

所以我们要在原数组上进行操作问题简化为两步：

其一：把当前节点的next域：由指向下一个转换为指向上一个！

结合题目的实例分析原来二号结点的next域 里面存放的 是 三号结点的位置（也就是去哪儿能找到三号节点。三号节点的门牌号，三号节点作为对象把自己的引用赋值给node2.next

）

链表的真实结构及其存储方式如下

 所以我们将原来指向第三个结点的指向第一个，之后我们继续，将第三个中原来指向第四个的修改为指向第二个！

这时候我们发现：我们遍历链表是环环相扣的，我们遍历链表是根据上一个结点中next域中存的地址去找下一个结点，（如本示例中根据二号结点的next去找三号结点，但二号结点的next已经被修改指向了一号节点，所以我们需要存储二号节点的下一个结点的位置。将其保存起来，使链表能正常遍历下去）这也就是我们需要解决的第二个问题

 至此，问题分析结束！

伪代码实现

暂存当前的下一个结点         tempt   （temp point to）

当前指向                                 cur        （current)

当前指向的之前的结点          prve         

 while(?)
 
{
 
       // 暂存当前的下一个结点遍历
 
         tempt=cur.next;//先存起来再说，确保后续正常向下进行遍历
 
        cur.next=prev；
 
        prev=prev;
 
        cur=cur.next;
 
}

        

 当前指向第二个，对2进行操作，先把第三个的位置交给tempt存起来，确保正常进行！

tempt = cur.next；

 然后可以放心大胆的操作

       

 框起来的这个我们就不要啦！

把他换成指向前面的

 此处的代码是

cur.next = prev;

 第二个倒转完毕后

向着后续的冲啊！

prev=cur;//此处保证prev始终指向cur指向的前一个
cur=tempt;//预先存起来的发挥作用，保证正常进行！

那么我们的while循环里面的终止条件也出来了！

即：cur==null 

此处也巧妙地避开了特殊情况：1）链表为空，不进循环，直接返回head = null；

·     2）链表只有一个结点 不进入循环 直接返回头结点，不用倒置！

我们还发现链表结点数大于等于两个的时候，第一个结点的next域还是指向第二个的，形成闭环循环

所以我们在一开始将tempt赋值为null

第一次将头结点的next域修改为空 

//编者注：其实很多时候我们不知道对象赋值什么就先给个null，此处正好是引用为空，第一次修改起到妙用！

 

 

最后题目要求返回新的头结点

当结点个数大于等于两个时，

新头结点就是最后一个结点，单链表中最后一个结点的特点就是next域名为空，所以遇到cur.next==null；

记录下来就可以了！

---

代码实现

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        ListNode tempt   = null;
        ListNode cur     = head;
        ListNode prev    = null;
 
        while(cur != null){
            if(cur.next==null){
                newHead = cur;
            }
            tempt = cur.next;
            cur.next = prev;
            prev = cur;
            cur = tempt;
        }
 
        return newHead;
 
    }
}