一、题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?


二、解决方法

方法一:双指针迭代

思路:可以申请两个指针,第一个指针叫 prev,最初是指向 null 的。第二个指针 curr 指向 head,然后不断遍历 curr。每次迭代到 curr,都将 curr 的 next 指向 prev,然后 prev 和 curr 前进一位。都迭代完了(curr 变成 null 了),prev 就是最后一个节点了。
动画演示如下:

代码如下(accepted):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* reverseList(struct ListNode* head) 
{
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    while (curr != NULL)
    {
        struct ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

复杂度分析:

  • 时间复杂度:O(n)O(n),假设 nn 是列表的长度,时间复杂度是 O(n)O(n)
  • 空间复杂度:O(1)O(1)

方法二:递归实现

思路:递归的两个条件:

  • 终止条件是当前节点或者下一个节点等于null
  • 在函数内部,改变节点的指向,也就是 head 的下一个节点指向 head 递归函数那句
    head.next.next = head
    很不好理解,其实就是 head 的下一个节点指向head。
    递归函数中每次返回的 cur 其实只最后一个节点,在递归函数内部,改变的是当前节点的指向。

动画演示如下图所示:

代码如下:

struct ListNode* reverseList(struct ListNode* head) 
{
    // 递归终止条件是当前节点为空,或下一个节点为空
    if (head == NULL || head->next == NULL)
        return head;
    // 这里的cur就是最后一个节点
    struct ListNode* cur = reverseList(head->next);
    /*
     这里请配合动画演示理解,如果链表是 1->2->3->4->5,
     那么此时的 cur 就是5,而 head 是4,head 的下一个是5,
     下下一个是空,所以 head.next.next 就是5->4
    */
    head->next->next = head;
    // 防止链表循环,需要将 head.next 设置为空
    head->next = NULL;
    // 每层递归函数都返回 cur,也就是最后一个节点
    return cur;
}

复杂度分析

  • 时间复杂度:O(n)O(n),假设 nn 是列表的长度,那么时间复杂度为 O(n)O(n)
  • 空间复杂度:O(n)O(n),由于使用递归,将会使用隐式栈空间。递归深度可能会达到 nn 层。