反向单链表一直以来是Java面试问题之一。在 Java 中逆转单链表涉及迭代列表并改变节点间链接的方向。
方法1：下面是一个使用迭代方法的简单实现：
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public class ReverseLinkedList {
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
ListNode next = null;
while (current != null) {
next = current.next; // Save the next node
current.next = prev; // Reverse the link
prev = current; // Move to the next nodes
current = next;
}
// prev "现在指向反转列表的新首部
return prev;
}
// Helper method to print the linked list
public static void printList(ListNode head) {
ListNode current = head;
while (current != null) {
System.out.print(current.val + " ");
current = current.next;
}
System.out.println();
}
public static void main(String[] args) {
// Example usage
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
System.out.println("Original Linked List:");
printList(head);
// 反转链接列表
head = reverseList(head);
System.out.println("Reversed Linked List:");
printList(head);
}
}
|
在本例中，reverseList 方法将链表的首部作为输入，迭代地反转节点之间的链接方向。printList 方法是一个辅助函数，用于打印链表中的元素以供验证。
方法2：使用compareTo()方法：
public class Node<T> implements Comparable<T> {
private T NodeValue;
private Node<T> nodeNextReference;
public T getValue() {
return NodeValue;
}
public void setValue(T nodeValue) {
this.NodeValue = nodeValue;
}
public Node<T> GetNextReference() {
return nodeNextReference;
}
public void SetNextRef(Node<T> nodeNextReference) {
this.nodeNextReference = nodeNextReference;
}
// @Override indicates that a method declaration is intended to override a method declaration in a supertype.
@Override
public int compareTo(T nodeValue) {
if (nodeValue == this.NodeValue) {
return 0;
} else {
return 1;
}
}
}
|
主程序：
public class ReverseLinkedList<T> {
private Node<T> headElement;
// 遍历 Node 中的元素
public void IterateElement() {
Node<T> tempVariable = headElement;
while (true) {
if (tempVariable == null) {
break;
}
print(tempVariable.getValue() + " ");
tempVariable = tempVariable.GetNextReference();
}
}
// Reverse elements in Node
public void ReverseElement() {
println("\nReversing Linked List now...\n");
Node<T> previousElement = null;
Node<T> currentElement = headElement;
Node<T> nextElement = null;
while (currentElement != null) {
nextElement = currentElement.GetNextReference();
currentElement.SetNextRef(previousElement);
previousElement = currentElement;
currentElement = nextElement;
}
headElement = previousElement;
}
// 为节点添加元素
public void AddElement(T element) {
Node<T> Node = new Node<T>();
Node.setValue(element);
println("Adding Element: " + element);
Node<T> tempVariable = headElement;
while (true) {
if (tempVariable == null) {
headElement = Node; // 只有一个元素？头部和尾部指向相同
break;
} else if (tempVariable.GetNextReference() == null) {
tempVariable.SetNextRef(Node);
break;
} else {
tempVariable = tempVariable.GetNextReference();
}
}
}
// 主要测试方法
public static void main(String a[]) {
ReverseLinkedList<Integer> LinkedList = new ReverseLinkedList<Integer>();
int RandomNo;
println("in main()...\n");
// 让我们创建一个包含 15 个值的整数数组
for (int i = 1; i <= 8; i++) {
RandomNo = (21 + (int) (Math.random() * ((55 - 2)))); // We are just getting total 8 Random elements
LinkedList.AddElement(RandomNo);
}
println("\nOriginal Linked List:");
LinkedList.IterateElement();
println("");
LinkedList.ReverseElement();
println("Reversed Linked List:");
LinkedList.IterateElement();
}
// 带有新行的简单日志工具
private static void println(String string) {
System.out.println(string);
}
// Simple Log utility
private static void print(String string) {
System.out.print(string);
}
}
|