大家都知道，说到数据结构，那么链表，是肯定绕不开的。而说到链表，那么反转链表，更是肯定绕不开的了。今天笔者这边就分享一下自己对反转链表的看法，笔者自己觉得这个思路很好理解（当然，到目前为止只有我自己这么觉得，哈哈）
我们这次只讨论单向链表。简单提一下，单向链表，每个节点，有两个部分组成，一个部分是存储该节点的value的，另一个部分是存储指针的，指针就是指向下一个节点的地址。像连续型空间和非连续型空间等问题这里就不展开讨论了，重点解决一个问题，那就是如何实现反转链表，具体的每一步是怎么做的。
public Node reverse(Node head){
Node pre = null; ----------------------------------1
Node next = null; ----------------------------------2
while(head != null){ --------------------------------3
next = head.next; -------------------------------4
head.next = pre; -----------------------------------5
pre = head; ------------------------------------------6
head = next; ---------------------------------------7
}
return pre;
}
下图假如说是我们的链表，节点分别是A,B,C。很明显，现在的头结点是A。
现在的顺序是A->B->C->null，那么反转后的顺序是，C->B->A->null
代码中的1,2行，是我们新创建的两个节点，他们主要是起一个记录的作用。
第三行，while循环里面的条件，主要用来判断，我们的反转操作针对的对象，是否已经到了null了，因为null是链表的最后一位的指向。
第四行的代码，实际是为了第五行。为什么这么说呢，因为第五行，要把A这个节点，指向pre，而此时的pre=null，也就是说要把之前的A.next = B,换成A.next=null。而我们的入参head,它实际就是链表上的一个节点，如果我们直接A.next = pre了，那么我们就没法去获取到B了，要知道，B之前才是A.next去获取的。所以第四行，实际是对B的一个保留。让我们既可以改变A的指针，改为指向pre，同时又可以保留住之前的B这个节点的数据。
到第五行为止，其实我们的第一个反转，就已经完成了。但是为了下一次反转，我们不得不去做一些相关的准备工作。也就是第6~7行的代码。
第六行，改变了pre的值，改为了A，第七行，将head的值改为了B。目前的链表，如下图
而第二次while循环开始了，第四行的代码，保存了C的值，第五行的代码，则是将B的指针，指向了A，因为A此时是pre了。接下来第六行，B成了pre了，而head成了C了。到这一步为止，我们的A,B的反转，就完成了，接下来会在C节点，发生一样的逻辑，就是C的指针指向了B，再下一次while循环，则是head=null了，那么循环就会结束。而这时，我们的链表反转也完成了。
感谢您的观看~
网友评论