用java设计一个算法利用栈的基本运算将一个整数链栈中所有元素逆置。例如链栈st中元素从栈底到栈顶为(1,2,3,4),逆置后为(4,3,2,1)
时间: 2024-12-10 21:50:20 浏览: 15
在 Java 中,我们可以使用两个栈来实现这个操作。一个栈用于存放链表中的元素,另一个空栈用于存储逆序后的元素。下面是具体的步骤:
1. 初始化两个栈 `srcStack` 和 `dstStack`。
2. 遍历链栈 `st`,依次将每个元素压入 `srcStack`。
3. 当遍历完 `st` 后,开始弹出 `srcStack` 的元素并压入 `dstStack`,即完成逆序过程。
4. 最后,`dstStack` 的顶部元素就是逆序后的第一个元素。
以下是 Java 代码示例:
```java
import java.util.Stack;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head; // 如果链表为空或只有一个节点,则无需反转
Stack<ListNode> srcStack = new Stack<>();
Stack<ListNode> dstStack = new Stack<>();
// 入栈原始链表
ListNode curr = head;
while (curr != null) {
srcStack.push(curr);
curr = curr.next;
}
// 出栈并反转
curr = dstStack.isEmpty() ? null : srcStack.pop(); // 初始化反转后的头结点
while (!srcStack.isEmpty()) {
ListNode temp = srcStack.pop();
temp.next = curr;
curr = temp;
}
return dstStack.isEmpty() ? null : curr; // 返回反转后的链表头
}
```
阅读全文