温馨提示×

java怎么实现单向链表反转

小亿
82
2023-12-11 14:03:41
栏目: 编程语言

要实现单向链表的反转,可以采用迭代或递归的方式来实现。以下是使用迭代的方式实现单向链表的反转的Java代码:

public class LinkedList {
    private Node head;

    public void reverse() {
        Node prev = null;
        Node current = head;
        Node next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }

    // Node class
    private static class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }
}

使用上述代码,可以通过调用reverse方法来实现单向链表的反转。

另外,以下是使用递归的方式实现单向链表的反转的Java代码:

public class LinkedList {
    private Node head;

    public void reverse() {
        head = reverse(head, null);
    }

    private Node reverse(Node current, Node prev) {
        if (current == null) {
            return prev;
        }
        Node next = current.next;
        current.next = prev;
        return reverse(next, current);
    }

    // Node class
    private static class Node {
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
        }
    }
}

使用上述代码,同样可以通过调用reverse方法来实现单向链表的反转。

无论是迭代还是递归的方式,都需要定义一个Node类来表示链表的节点,其中包含一个数据域和一个指向下一个节点的指针。在反转时,需要使用三个指针来记录当前节点、前一个节点和下一个节点,通过修改节点之间的指针来实现反转操作。

0