1.简介
在本教程中，我们将在Java中实现两个鍊表反转算法。
2.鍊表数据结构
鍊表是一种线性数据结构，其中每个元素中的指针确定顺序。链接列表的每个元素都包含一个用于存储列表数据的数据字段和一个指向该序列中的下一个元素的指针字段。另外，我们可以使用head指针指向链接列表的开始元素：
反转鍊表之后， head将指向原始鍊表的最后一个元素，而每个元素的指针将指向原始鍊表的前一个元素：
在Java中，我们有一个LinkedList类来提供List和Deque接口的双链列表实现。但是，在本教程中，我们将使用常规的单链列表数据结构。
让我们首先从ListNode类开始，以表示链接列表的元素：
public class ListNode {
private int data;
private ListNode next;
ListNode(int data) {
this.data = data;
this.next = null;
}
// standard getters and setters
}ListNode类具有两个字段：
- 代表元素数据的整数值
- 指向下一个元素的指针/引用
鍊表可能包含多个ListNode对象。例如，我们可以使用循环构造以上示例链接列表：
ListNode constructLinkedList() {
ListNode head = null;
ListNode tail = null;
for (int i = 1; i <= 5; i++) {
ListNode node = new ListNode(i);
if (head == null) {
head = node;
} else {
tail.setNext(node);
}
tail = node;
}
return head;
}3.迭代算法的实现
让我们用Java实现迭代算法：
ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
while (current != null) {
ListNode nextElement = current.getNext();
current.setNext(previous);
previous = current;
current = nextElement;
}
return previous;
}在此迭代算法中，我们使用两个ListNode变量previous和current来表示鍊表中的两个相邻元素。对于每次迭代，我们都将这两个元素反转，然后移至下两个元素。
最后， current指针将为null,而previous指针将是旧鍊表的最后一个元素。因此， previous也是反向链接列表的新头指针，我们从方法中将其返回。
我们可以用一个简单的单元测试来验证这种迭代实现：
@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseList(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}在此单元测试中，我们首先构造一个具有五个节点的示例链接列表。另外，我们验证鍊表中的每个节点都包含正确的数据值。然后，我们调用迭代函数来反向链接列表。最后，我们检查反向链接列表，以确保数据按预期反向。
4.递归算法的实现****
现在，让我们在Java中实现递归算法：
ListNode reverseListRecursive(ListNode head) {
if (head == null) {
return null;
}
if (head.getNext() == null) {
return head;
}
ListNode node = reverseListRecursive(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return node;
}在reverseListRecursive函数中，我们以递归方式访问链接列表中的每个元素，直到到达最后一个元素。最后一个元素将成为反向链接列表的新标题。同样，我们将受访元素附加到部分反向鍊表的末尾。
同样，我们可以使用简单的单元测试来验证此递归实现：
@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseListRecursive(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}
0 评论