欢迎访问宙启技术站
智能推送

如何使用Java实现一个单链表反转函数?

发布时间:2023-09-11 05:16:02

要实现一个单链表的反转函数,需要使用Java语言编写以下步骤:

1. 定义一个节点类,包含一个存储数据的变量和一个指向下一个节点的指针。

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        next = null;
    }
}

2. 定义一个单链表类,包含一个指向头节点的指针。

class LinkedList {
    Node head;

    LinkedList() {
        head = null;
    }
}

3. 实现单链表的反转函数。遍历原链表,将每个节点的指针指向前一个节点。

class LinkedList {
    //...

    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; // 更新头节点为反转后的链表的头节点
    }
}

4. 编写测试代码,创建一个单链表对象并添加若干节点,然后调用反转函数进行链表反转。

class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        list.head.next = second;
        second.next = third;

        System.out.println("原链表:");
        list.printList();

        list.reverse();
        System.out.println("反转后的链表:");
        list.printList();
    }
}

完整代码如下所示:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        next = null;
    }
}

class LinkedList {
    Node head;

    LinkedList() {
        head = null;
    }

    void printList() {
        Node current = head;

        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    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;
    }
}

class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);

        list.head.next = second;
        second.next = third;

        System.out.println("原链表:");
        list.printList();

        list.reverse();
        System.out.println("反转后的链表:");
        list.printList();
    }
}

输出结果为:

原链表:
1 2 3
反转后的链表:
3 2 1

通过以上步骤,我们就实现了一个使用Java语言编写的单链表反转函数。