单链表反转
很多时候工作和面试的时候都会遇到类似的单链表反转的情况，今天就参考写了一个,类似数据结构和算法的知识，最主要的不是代码而是思路和思维方式；尽管这方面我也只是很普通的一位，于是在努力进步的道路上。
实现的两种方式:主要是以java形式来实现。
递归方式
反转的本质是指向方向比如 A->B->C->D 那么递归来实现，判断如果后面还有元素，那么就先让后面的元素反转，进而向前递归，先反转A但是A下一个元素有B所以就先反转B但是B下一个元素是C，以此类推，最先反转的是D. 代码实现
//递归
public static Node reverse(Node header){
if (header == null || header.getNext() == null){
return header;
}
Node rehead = reverse(header.getNext());// 先反转后一元素
header.getNext().setNext(header);//将当前节点指向前一节点
header.setNext(null);
return rehead;
}
非递归方式(遍历方式)
我们大部分人还是正向思维，也就是平时用的比较多的遍历思维，正向的思考，递归是反向的思维方式，计算机科学思维使用最多的方式之一。遍历代码实现如下：
public static Node reverse2(Node head) {
if (head != null) {
Node prevNode = head;//上一个节点
Node currentNode = head.getNext();//当前节点
Node tempNode;// 临时结点，用于保存当前结点（即下一结点）
while (currentNode != null) {
tempNode = currentNode.getNext();
currentNode.setNext(prevNode);//反转指向
//指向移动
prevNode = currentNode;
currentNode = tempNode;
}
head.setNext(null);
return prevNode;
}
return null;
}
肯定会说搞一个完整的代码运行下就啥也明白了，是的完整代码下面就有，还是希望读者可以先理解思路和简单的实现方式或者代码片段，最后再用完整的代码来看效果便于记忆。完整代码实现：
public class Node {
private String data;
private Node next;
public Node(String data,Node next){
this.data = data;
this.next = next;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public static void main(String[] args) {
Node nodeE = new Node("E",null);
Node nodeD = new Node("D",nodeE);
Node nodeC = new Node("C",nodeD);
Node nodeB = new Node("B",nodeC);
Node nodeA = new Node("A",nodeB);
Node node = nodeA;
while (node != null){
System.out.println(node.data);
node = node.getNext();
}
System.out.println("------------------------");
Node nodeW = reverse(nodeA);
while (nodeW != null){
System.out.println(nodeW.data);
nodeW = nodeW.getNext();
}
}
//递归
public static Node reverse(Node header){
if (header == null || header.getNext() == null){
return header;
}
Node rehead = reverse(header.getNext());// 先反转后一元素
header.getNext().setNext(header);//将当前节点指向前一节点
header.setNext(null);
return rehead;
}
//遍历
public static Node reverse2(Node head) {
if (head != null) {
Node prevNode = head;//上一个节点
Node currentNode = head.getNext();//当前节点
Node tempNode;// 临时结点，用于保存当前结点（即下一结点）
while (currentNode != null) {
tempNode = currentNode.getNext();
currentNode.setNext(prevNode);//反转指向
//指向移动
prevNode = currentNode;
currentNode = tempNode;
}
head.setNext(null);
return prevNode;
}
return null;
}
}
很多时候大家遇到问题第一件事情基本都是在找直接可以用的答案，然而大虾或者大侠们第一个想到的是思路，理解以及思维方式的锻炼。从中涉及到的知识点或者原理，如果我们也类似迷茫或者懒堕的伸手党，那我们也需要做出点什么改变来尝试一下，也许会有意想不到的惊喜。以上写法参考https://blog.csdn.net/guyuealian/article/details/51119499
后来发现一个更为简洁的代码实现可以参考:https://www.cnblogs.com/tina-smile/p/4878983.html
网友评论