链表的反转（循环遍历实现）

前言

链表的反转问题在校招中算是一个高频题目，同时考的比较勤的还有：Top K ，快排，堆排，这些在以后的帖子中我们再细说，今天我们先用 Java 实现单链表的反转。

单链表的反转

链表的反转有两种实现：遍历，递归；

遍历易于理解，递归代码简洁，各有千秋。

反转的遍历实现

  // 单链表反转 (遍历的实现)
    private  void reverseByLoop(){
        if (first==null){
            return;
        }
        // 前一个节点
        List p=first;
        // 当前节点
        List q=first.next;
        //存储下一节点
        List temp;
        //当first=null，出现环 ，输出：23,10,23,10
        first.next=null;

        //当 q为 null,则p是尾节点
        while (q!=null){
             temp=q.next;

             // 改变当前指针的指向，从指向 next 变成指向 pre
             q.next=p;

             // 移动当前指针和下一指针
            p=q;
            q=temp;
        }
        //此时 p 最后一个结点 ，也是新的头结点
         first=p;

    }

捕获.PNG