题目信息

问题：如何实现一个高效的单向链表逆序输出？
出题人：阿里巴巴出题专家：昀龙／阿里云弹性人工智能负责人

代码

分别用C语言和Java完成了该题目，题目在Leetcode上难度是简单。

1. 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;
}

2. 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;
    }
}

总结

递归与栈结构两种的空间复杂度都比较低，但是时间复杂度很高。
网友们有更加好的方法，值得学习。

视频教程

视频教程