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

前言

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

推荐看看这个 看图理解单链表的反转，写得简单清晰。

单链表的反转

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

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

反转的遍历实现

在遍历时，要分清头指针 first （有的教程里写成 head ） 和第一个结点的区别，first 指向第一个结点，它只是一个指针。

  // 单链表反转 (遍历的实现)
    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;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29