图解反转单向链表【转载】

系统管理员 2022-04-18 01:48 182阅读 0赞

我总觉的反转链表的过程不是那么好理解，花了点时间画图来帮助理解。

节点类如下：

public class Node {
        public int value;
        public Node next;
    
        public Node(int data){
            this.value = data;
        }
    }

反转单向链表的函数如下：

public Node reverseList(Node head){
    
        Node pre = null;
        Node next = null;
    
        while (head != null) {
    
            next = head.next;
    
            head.next = pre;
    
            pre = head;
    
            head = next;
        }
    
        return pre;
    }

可以看到四行代码：

next = head.next; //1
    
    head.next = pre; //2
    
    pre = head; //3
    
    head = next; //4

现在有一个单向链表如下图所示：

![正向链表][SouthEast]

反转后如下所示：  
![反向链表][SouthEast 1]

接下来解析反转函数：  
![反转单向链表1][1]  
第一步：next = head.next  
将 head.next 赋值给 next 变量，也就是说 next 指向了节点2，先将节点2 保存起来。

第二步：head.next = pre  
将 pre 变量赋值给 head.next，即 节点1 指向了 null

第三步：pre = head

将 head 赋值给了 pre，即 pre 指向节点1，将节点1 设为“上一个节点”

第四步：head = next

将 next 赋值给 head，即 head 指向了节点2。将节点2 设为“头节点”

第一次循环完毕，进入第二次循环，如下图  
![反转单向链表2][2]  
第一步：next = head.next  
将 head.next 赋值给 next 变量，也就是 next 指向了节点3，先将节点3 保存起来。

第二步：head.next = pre  
将 pre 赋值给 head.next，pre 在上一次循环的时候指向了节点1，那么这一步的意义就是节点2 指向了 节点1，**完成一次反转**

第三步：pre = head

将 head 赋值给了 pre，即 pre 指向节点2，将节点2 设为“上一个节点”

第四步：head = next

将 next 赋值给 head，即 head 指向了节点3。将节点3 设为“头节点”

第二次循环完毕，以此类推！第三次第四次第五次循环。最后反转成如下图  
![完成反转][SouthEast 2]

## **总结** ##

*  保存当前头节点的下一个节点（当前头节点为2，先将节点3 保存起来）
 *  将当前头节点的下一个节点指向 “上一个节点”（当前头**节点2** 指向了 (“上一个节点”)**节点1**），这一步才是实现反转
 *  将当前头节点设置 “上一个节点”（将节点2 设为“上一个节点”）
 *  将保存的下一个节点设置 “头节点”（将节点3 设为“头节点”）

转载自：  
[https://blog.csdn.net/xyh269/article/details/70238501][https_blog.csdn.net_xyh269_article_details_70238501]

[SouthEast]: /images/20220418/54a39cbb5c744dc4bfe0a33dc4cc2f90.png
[SouthEast 1]: /images/20220418/088a5a7fe3b84160b8a2bc71bb64db39.png
[1]: /images/20220418/d4a8e6356eb9403c9cc171b037b8986c.png
[2]: /images/20220418/924a7d546d354b0faf82995fb4c91d2b.png
[SouthEast 2]: /images/20220418/5e44eab693554f38b008f1b9bd5541b7.png
[https_blog.csdn.net_xyh269_article_details_70238501]: https://blog.csdn.net/xyh269/article/details/70238501