如何使用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语言编写的单链表反转函数。
