单链表反转

单链表反转

很多时候工作和面试的时候都会遇到类似的单链表反转的情况，今天就参考写了一个,类似数据结构和算法的知识，最主要的不是代码而是思路和思维方式；尽管这方面我也只是很普通的一位，于是在努力进步的道路上。

实现的两种方式:主要是以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