Java中数组、字符串和链表的翻转方法详解207

在Java编程中，翻转（reverse）操作是一个常见的任务，它涉及到将数组、字符串或链表中的元素顺序颠倒。本文将深入探讨Java中实现数组、字符串和链表翻转的各种方法，并分析其效率和适用场景。我们将涵盖从简单的迭代方法到利用Java自带的集合类库函数的多种技术，并对每种方法进行代码示例和性能分析。

一、数组翻转

翻转数组是最基本的翻转操作之一。我们可以使用多种方法来实现，其中最常见的是双指针法和集合类库方法。

1.1 双指针法：

双指针法是一种高效的原地翻转数组的方法。它使用两个指针，一个指向数组的起始位置，另一个指向数组的结束位置。然后，这两个指针不断交换它们指向的元素，直到两个指针相遇。```java
public static void reverseArray(int[] arr) {
int left = 0;
int right = - 1;
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
```

该方法的时间复杂度为O(n)，空间复杂度为O(1)，其中n是数组的长度。这是原地算法，非常高效。

1.2 () 方法：

Java的``类提供了一个`reverse()`方法，可以直接翻转`List`类型的数组。虽然它不是直接操作数组，但是可以方便地将数组转换为`List`，进行翻转后再转换回数组。```java
public static void reverseArrayUsingCollections(int[] arr) {
List list = new ArrayList();
for (int num : arr) {
(num);
}
(list);
for (int i = 0; i < ; i++) {
arr[i] = (i);
}
}
```

这种方法的时间复杂度也是O(n)，但是空间复杂度为O(n)，因为它需要创建一个新的`List`来存储数组元素。

二、字符串翻转

字符串翻转与数组翻转类似，但由于字符串是不可变的，我们需要创建一个新的字符串来存储翻转后的结果。

2.1 使用 StringBuilder：

`StringBuilder`类提供了`reverse()`方法，可以高效地翻转字符串。```java
public static String reverseString(String str) {
return new StringBuilder(str).reverse().toString();
}
```

此方法的时间复杂度为O(n)，空间复杂度为O(n)，因为它创建了一个新的`StringBuilder`对象。

2.2 字符数组转换：

可以将字符串转换为字符数组，使用双指针法翻转字符数组，然后再将字符数组转换回字符串。```java
public static String reverseStringUsingCharArray(String str) {
char[] charArray = ();
int left = 0;
int right = - 1;
while (left < right) {
char temp = charArray[left];
charArray[left] = charArray[right];
charArray[right] = temp;
left++;
right--;
}
return new String(charArray);
}
```

此方法的时间复杂度为O(n)，空间复杂度为O(n)，因为它创建了一个新的字符数组。

三、链表翻转

链表翻转比数组和字符串翻转更复杂，因为它需要修改链表节点的指针。

3.1 迭代法：

迭代法是翻转链表的一种常用方法。它使用三个指针：`prev`、`curr`和`next`。`prev`指向当前节点的前一个节点，`curr`指向当前节点，`next`指向当前节点的下一个节点。通过不断更新这三个指针，我们可以将链表翻转。```java
public static ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = ;
= prev;
prev = curr;
curr = next;
}
return prev;
}
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
```

此方法的时间复杂度为O(n)，空间复杂度为O(1)。

3.2 递归法：

递归法也可以翻转链表，但其空间复杂度为O(n)，因为它使用了递归调用的栈空间。```java
public static ListNode reverseListRecursive(ListNode head) {
if (head == null || == null) {
return head;
}
ListNode newHead = reverseListRecursive();
= head;
= null;
return newHead;
}
```

总结

本文详细介绍了Java中数组、字符串和链表的翻转方法。不同的数据结构和场景需要选择不同的方法，以达到最佳的效率。双指针法和`()`方法是数组和字符串翻转的最佳选择，而迭代法是翻转链表的首选方法。

选择哪种方法取决于具体的应用场景和性能需求。对于需要原地操作且追求高效率的场景，双指针法是首选；而对于追求代码简洁性的场景，可以使用`()`或`()`方法。对于链表的翻转，迭代法通常比递归法更有效率。

2025-06-14

上一篇：Java JAR包合并：方法、工具及最佳实践

下一篇：Java静态数组与动态数组：深入比较与应用场景