题目信息
问题：如何实现一个高效的单向链表逆序输出？
出题人：阿里巴巴出题专家：昀龙／阿里云弹性人工智能负责人
代码
分别用C语言和Java完成了该题目，题目在Leetcode上难度是简单。
- C语言代码采用的是递归法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
// 特殊情况, 原样返回
if (head == NULL || head->next == NULL) {
return head;
}
// 该题使用递归的方法
// 找到最后一个节点，作为新的头
// 而其他的节点接受反转
// 找到倒数第二个节点和最后一个节点
struct ListNode* curr = head;
struct ListNode* lastNode;
struct ListNode* lastSecondNode;
while (curr != NULL) {
// 最后一个节点
if (curr->next == NULL) {
lastNode = curr;
}
// 倒数第二个节点
else if (curr->next->next == NULL) {
lastSecondNode = curr;
}
curr = curr->next;
}
// 倒数第二个节点后面接 NULL， 作为最后一个节点
lastSecondNode->next = NULL;
// 递归部分 最后一个节点接上反转
lastNode->next = reverseList(head);
return lastNode;
}
- Java语言代码利用了栈结构后进先出的特点实现了链表的反转。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
// 特殊情况
if (head == null || head.next == null) {
return head;
}
// 用栈来做这题
Stack<ListNode> stack = new Stack<>();
// 将所有节点压入栈
ListNode curr = head;
while (curr != null) {
stack.push(curr);
curr = curr.next;
}
// 最后一个节点作为新的头
ListNode newHead = stack.peek();
while (!stack.isEmpty()) {
// 指针指向弹出的节点
ListNode node = stack.pop();
// 弹出后栈空了
if (stack.isEmpty()) {
node.next = null;
}
else {
node.next = stack.peek();
}
}
// 返回新的 head
return newHead;
}
}
总结
递归与栈结构两种的空间复杂度都比较低，但是时间复杂度很高。
网友们有更加好的方法，值得学习。
