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

发表于

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

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

先看看Node节点把

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
复制代码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;
    }

}

看看链表反转递归方法

1
2
3
4
5
6
7
8
9
10
11
12
复制代码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
  • 递归的实现总是这么的简单，代码简练就是递归的好处，而且逻辑易于处理，只要能够出找出一层的逻辑，然后找出特殊值和出口，一个递归就已经完成啦
  • 这里出口显然就是那个if，为的是找到最后一个节点，然后就可以开始往前递归反转，同时这个if可以排除参数只有一个节点，参数为null的情况。
  • 递归的栈累计到最高层的时候（递归本质是栈，每一次递归放入一个栈，如果这层运行结束，就会弹出，运行下一层），最后一个if结束以后， 开始反转， 反转的逻辑其实很简单， 吧当前节点的下一个节点指向自己，然后自己指向null

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
复制代码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;
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
复制代码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是为反转部分，然后通过俩个指针的配合，不断的右移直到前部反转

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码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函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
复制代码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);
}

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

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%