链表反转(Java三种实现方式)

in 网站建设
关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9

链表这个数据结果经常遇见,这里提供一个链表反转的java代码实现,有三种算法,一种是递归的,俩种是非递归的。

首先为了方便测试,在博文最后贴上递归实现链表创建的代码,以供读者快速上手测试,提供的代码可以复制以后直接测试

先看看Node节点把

public class Node {
    //链表用于存储值
    private final int value;
    //指向下一个节点  理解为Node next更加恰当
    private Node node;

    public Node(int value) {
        this.value = value;
        this.node = null;
    }

    public int getValue() {
        return value;
    }

    public Node getNode() {
        return node;
    }

    public void setNode(Node node) {
        this.node = node;
    }

}

看看链表反转递归方法

public Node reverserLinkedList(Node node){
        if (node.getNode() == null || node == null){
            return node;
        }
        Node newdata = reverserLinkedList(node.getNode());
        node.getNode().setNode(node);
        node.setNode(null);
        return newdata;
}
    //这个递归,返回值只是为了控制返回的是最后一个节点
    //然后通过递归通过栈的特性,这里就是让它可以从最后一个节点开始把自己的子节点的子节点改成自己
    //自己的子节点改为null

说完了递归的算法,也了解递归其实就是栈,现在就用相同的逻辑,只不过把递归变成循环,用java本身实现的Stack数据结构编写一个更加高效的代码

public Node reverserLinkedList2(Node node){
    Stack<Node> nodeStack = new Stack<>();
    Node head = null;
    //存入栈中,模拟递归开始的栈状态
    while (node != null){
        nodeStack.push(node);
        node = node.getNode();
    }
    //特殊处理第一个栈顶元素(也就是反转前的最后一个元素,因为它位于最后,不需要反转,如果它参与下面的while,因为它的下一个节点为空,如果getNode(), 那么为空指针异常)
    if ((!nodeStack.isEmpty())){
        head = nodeStack.pop();
    }
    //排除以后就可以快乐的循环
    while (!nodeStack.isEmpty()){
        Node tempNode = nodeStack.pop();
        tempNode.getNode().setNode(tempNode);
        tempNode.setNode(null);
    }
    return head;
}

逻辑一目了然,备注上面的解释已经很清楚啦

还有一个循环写法更加简单,使用俩个指针,不需要栈结构

public Node reverserLinkedList3(Node node){
    //指向空,可以想象成位于第一个节点之前
    Node newNode = null;
    //指向第一个节点
    Node curNode = node;

    //循环中,使用第三变量事先保存curNode的后面一个节点

    while (curNode != null){
        Node tempNode = curNode.getNode();
        //把curNode反向往前指
        curNode.setNode(newNode);
        //newNode向后移动
        newNode = curNode;
        //curNode 向后移动
        curNode = tempNode;
    }

    return newNode;
}

这个的思路就是 俩个指针,把一个链表分成俩个部分, newNode是已经反转部分,curNode是为反转部分,然后通过俩个指针的配合,不断的右移直到前部反转

现在贴其他代码部分啦,先贴链表构建的

public class LinkedListCreator {
    //构建函数
    public Node createLinkedList(List<Integer> list){
        if (list.isEmpty()){
            return null;
        }
        Node headNode = new Node(list.get(0));
        Node tempNode = createLinkedList(list.subList(1, list.size()));
        headNode.setNode(tempNode);
        return headNode;
    }

    //测试方便的打印函数
    public void printList(Node node){
        while (node != null){
            System.out.print(node.getValue());
            System.out.print(" ");
            node = node.getNode();
        }
        System.out.println();
    }
}

main函数

public static void main(String[] args) {
    LinkedListCreator linkedListCreator = new LinkedListCreator();
    Node node = linkedListCreator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5));
    Node node2 = linkedListCreator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5));
    Node node3 = linkedListCreator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5));
    LinkedListReverser linkedListReverser = new LinkedListReverser();

    Node res = linkedListReverser.reverserLinkedList(node);
    Node res2 = linkedListReverser.reverserLinkedList2(node2);
    Node res3 = linkedListReverser.reverserLinkedList3(node3);

    linkedListCreator.printList(res);
    linkedListCreator.printList(res2);
    linkedListCreator.printList(res3);
}

博文是作者原本在其他平台的,现迁移过来

关注公众号【好便宜】( ID:haopianyi222 ),领红包啦~
阿里云,国内最大的云服务商,注册就送数千元优惠券:https://t.cn/AiQe5A0g
腾讯云,良心云,价格优惠: https://t.cn/AieHwwKl
搬瓦工,CN2 GIA 优质线路,搭梯子、海外建站推荐: https://t.cn/AieHwfX9
扫一扫关注公众号添加购物返利助手,领红包
Comments are closed.

推荐使用阿里云服务器

超多优惠券

服务器最低一折,一年不到100!

朕已阅去看看