链表反转解法

背景

当初大二学习数据结构的时候，有许多数据结构我都学得有点懵，总感觉没有一个系统的概括和总结，导致我的链表学得一般。后来班上有个同学微信跟我说叫我关注”程序员小灰”这个公众号，说他讲得很生动形象，最后关注了一波，看了他里面一道经典的面试题——链表反转。接下来就来讲解链表反转的解法。

链表反转图示

解法说明

1. 链表反转的本质其实就是把每一个节点原本指向下一个节点的next的指针，反转过来指向它的前置节点。

   

2. 进行链表反转的时候，需要同时知道三个节点才能进行反转。

   

解法步骤

1. 以p2节点为根，把p2节点原本指向p3的next指针反转，指向p1

   

2. 三个临时节点引用p1，p2，p3分别向后移动一位

   

3. 重复”1”的工作，以p2节点为根，把p2节点原本指向p3的next指针反转，指向p1

   

4. 重复”2”的工作，三个临时节点引用p1，p2，p3分别向后移动一位

   

5. 继续重复以上的工作，一直到p2为空为止

   

6. 最后，把head节点的next指向空，成为反转链表的尾节点。并把p1赋值给head，让p1所在节点成为反转链表的头节点

   

​ 听完上面的讲解，估计有点懵逼，来看看代码的实现，再结合上面的图示步骤，相信你就会理解链表反转了

代码实现

public class ListNode{
    int val;
    ListNode next = null;
    
    ListNode(int val){
        this.val = val;
    }
}

public class Solution{
    public ListNode ReverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode p3 = null;
        while(p2 != null){
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        head.next = null;
        head = p1;
        return head;
    }
}

总结

对于链表的反转就介绍到这里，感谢大家的支持。嘻嘻嘻~~~

参考来源

• 程序员小灰公众号
• 牛客网原题链接