Java 实现反转一个链表

心已赠人 2023-10-12 14:13 51阅读 0赞

#### 文章目录 ####

*  思路
 *  核心四步骤
 *  循环移动
 *  代码实现

## 思路 ##

翻转指的是改变链表中结点的指向，而不是将它的数据反转。  
  
![26c5fd9277e5467e86da66958892747a.png_pic_center][]  
上图展示出的就是一个反转前的链表，下图展示一个反转后的链表。  
  
![a4d0463e5b794d13b90ce09650129c2b.png_pic_center][]  
根据上图可以看出，结点的地址和数据都没有改变，改变的只是链表结点的指向，更改后的头结点变成了尾结点。  
  
首先要定义一个 **cur** 变量，让这个变量指向 **head 结点** 的下一个结点。  
接着就是将 head 结点置为空，也就是将 head 结点地址域保存的地址改为 null 即可。  
  
![e4c190d8c96d4341bc05119cd381fdfe.png_pic_center][]  
链表中的 head 结点原本保存的是 0x11 这个地址，但是现在改为了 null，表示与后面的结点断开了连接。

cur 这个变量指向的就是 head 结点的下一个结点，由于 head 结点地址域里保存的地址改为 null 就与后面结点断开连接了，此时为了保证 cur 可以成功指向，因此需要先将 cur 移动，然后再改 head 结点的地址域。  
  
接下来要做的就是将 cur 指向的结点和它后面的结点全部移动到 head 结点前面即可。

需要注意的是 **如果链表一开始就是空的，直接返回 null即可，因为空的链表无法反转**。  
**如果此时的链表只有一个结点，也不需要反转，因为一个结点再怎么反转也没有变化**。

## 核心四步骤 ##

核心四步骤分别是 ：

> **1.curNext = cur.next  
> 2.cur.next = head  
> 3.head = cur  
> 4.cur = curNext**

先定义的 **curNext** 始终指向 **cur.next**，curNext 是为了保证将所有的结点都移动到 head 结点的前面去，实现的一个类似于记录的功能。  
  
![16e125931ad643d5bcefc741ea3d105a.png_pic_center][]  
先将 cur 结点移动到 head 结点的前面，只需要更改 cur 结点地址域中的保存的地址即可，  
接着是将 head 指向 cur 指向的结点。

此时第一个结点就已经移动完成了，但是会发现如果还想要移动其他的结点的话其实是无法实现了。  
因为此时原本的 head 结点早与后面的结点断开了连接，此时是无法操作后面剩余结点的。  
  
此时四个核心步骤中的 **第一个** 和 **第四个** 就体现出了作用。  
  
首先将定义好的 **curNext** 指向并且始终指向 cur 结点的下一个结点。  
  
![9993ec47972e4b5fac2cb9768bd4ac89.png_pic_center][]  
可以看到此时 curNext 就指向了 cur 结点的下一个结点。  
  
接下来就是更改 cur 结点的指向，将它移动到 head 结点的前面。  
  
![3d523dbe5283426fba339c22b1c26e83.png_pic_center][]  
然后是将 head 指向 cur 指向的位置。  
  
![ace593dd7dbd4d90900f621e12ded1af.png_pic_center][]  
此时当我们打算移动其它结点的时候会发现，只需要将 cur 指向 curNext 即可访问到其他的结点了。  
这也就是和心步骤的第四步 **cur = curNext**。  
  
![355a6edd02f447d29b1ce30023d171ef.png_pic_center][]  
以上过程是把这四个步骤都走了一遍才会产生的结果，想要把所有的结点都移动到完毕，继续按照顺序执行上面的四个步骤即可。

## 循环移动 ##

想要将所有的结点全部移动完毕，实现一个循环即可，在这个循环里面去重复执行上述的四个步骤。  
  
![ea48f726f0214d45a1ae962e878a0e02.png_pic_center][]  
  
![88507fbb9bac4f92b520218c0c9227c7.png_pic_center][]  
当重复执行了几次循环之后，会发现此时的 cur 虽仍然是指向了 curNext，但是此时 cur 是为空的。  
我们此时又可以发现，链表已经反转完成了，因此循环的判定条件就是当 cur 不为空时就继续执行循环，若 cur 为空，也就是说明此时的链表已经反转成功了，跳出循环返回当前的 head 即可。

## 代码实现 ##

class MySingleNodeTest {
        
        static class ListNode{
        
            public int value;//数据
            public ListNode next;//地址
    
            public ListNode(int value) {
        
                this.value = value;
            }
        }
        //设置头结点
        public ListNode head;
        //创建链表
        public void createNode() {
        
            ListNode listNode1 = new ListNode(12);
            ListNode listNode2 = new ListNode(23);
            ListNode listNode3 = new ListNode(34);
            ListNode listNode4 = new ListNode(45);
    
            listNode1.next = listNode2;
            listNode2.next = listNode3;
            listNode3.next = listNode4;
    
            this.head = listNode1;//设置头结点
        }
        // 打印链表
        public void disPlay() {
        
            ListNode cur = this.head;
            while (cur != null) {
        
                System.out.print(cur.value + " ");
                cur = cur.next;//cur指向它的下一个
            }
            System.out.println();//换行
        }
    
        // 反转一个链表
        public ListNode reversalList() {
        
            // 如果链表是空的
            if (this.head == null) {
        
                return null;
            }
            // 如果只有一个结点不需要反转
            if (this.head.next == null) {
        
                return this.head;
            }
            // 创建一个 cur 指向头结点的后一个结点
            ListNode cur = this.head.next;
            // 将头结点置为空
            this.head.next = null;
            // 开始四个步骤移动 cur 和后面的结点
            while (cur != null) {
        
                ListNode curNext = cur.next;
                cur.next = this.head;
                head = cur;
                cur = curNext;
            }
            // 循环结束反转完成返回头结点即可
            return this.head;
        }
    }
    
    public class MySingleNode {
        
    
        public static void main(String[] args) {
        
            MySingleNodeTest mySingleNodeTest = new MySingleNodeTest();
            // 调用方法创建链表
            mySingleNodeTest.createNode();
            // 打印反转之前的链表
            mySingleNodeTest.disPlay();
    
            // 调用反转方法反转
            mySingleNodeTest.reversalList();
            // 打印反转之后的链表
            mySingleNodeTest.disPlay();
        }
    }

**(1) 反转之前情况：**

![3bfff268e52c42d48f2ee286cb3f0aa3.png_pic_center][]  
可以看到此时 头结点 中的数据是 12，而末尾结点中的数据是 45。  
  
此时对应的链表图解如下图：  
  
![26c5fd9277e5467e86da66958892747a.png_pic_center][]

**(2) 反转之后的情况：**

![1ac1a27cd8a44ba5a368b7fdb00d62c5.png_pic_center][]  
调用反转方法后，可以看到此时头结点中的数据变成了 45，而尾结点变成了 12。  
此时说明反转成功了。  
  
此时对应的链表图解如下图：  
  
![a4d0463e5b794d13b90ce09650129c2b.png_pic_center][]

[26c5fd9277e5467e86da66958892747a.png_pic_center]: https://img-blog.csdnimg.cn/26c5fd9277e5467e86da66958892747a.png#pic_center
[a4d0463e5b794d13b90ce09650129c2b.png_pic_center]: https://img-blog.csdnimg.cn/a4d0463e5b794d13b90ce09650129c2b.png#pic_center
[e4c190d8c96d4341bc05119cd381fdfe.png_pic_center]: https://img-blog.csdnimg.cn/e4c190d8c96d4341bc05119cd381fdfe.png#pic_center
[16e125931ad643d5bcefc741ea3d105a.png_pic_center]: https://img-blog.csdnimg.cn/16e125931ad643d5bcefc741ea3d105a.png#pic_center
[9993ec47972e4b5fac2cb9768bd4ac89.png_pic_center]: https://img-blog.csdnimg.cn/9993ec47972e4b5fac2cb9768bd4ac89.png#pic_center
[3d523dbe5283426fba339c22b1c26e83.png_pic_center]: https://img-blog.csdnimg.cn/3d523dbe5283426fba339c22b1c26e83.png#pic_center
[ace593dd7dbd4d90900f621e12ded1af.png_pic_center]: https://img-blog.csdnimg.cn/ace593dd7dbd4d90900f621e12ded1af.png#pic_center
[355a6edd02f447d29b1ce30023d171ef.png_pic_center]: https://img-blog.csdnimg.cn/355a6edd02f447d29b1ce30023d171ef.png#pic_center
[ea48f726f0214d45a1ae962e878a0e02.png_pic_center]: https://img-blog.csdnimg.cn/ea48f726f0214d45a1ae962e878a0e02.png#pic_center
[88507fbb9bac4f92b520218c0c9227c7.png_pic_center]: https://img-blog.csdnimg.cn/88507fbb9bac4f92b520218c0c9227c7.png#pic_center
[3bfff268e52c42d48f2ee286cb3f0aa3.png_pic_center]: https://img-blog.csdnimg.cn/3bfff268e52c42d48f2ee286cb3f0aa3.png#pic_center
[1ac1a27cd8a44ba5a368b7fdb00d62c5.png_pic_center]: https://img-blog.csdnimg.cn/1ac1a27cd8a44ba5a368b7fdb00d62c5.png#pic_center