题目描述

35.反转链表

方法1

链表，递归

reverseList，翻转链表后，返回新链表的头结点，也就是原链表的尾结点。

首先，可以先递归处理reverseList(head->next)，将以head->next为头结点的链表翻转，得到原链表的尾结点tail（新链表的头结点）。此时，head->next为新链表的尾结点，令它的next指向head（即head->next->next=head）。然后将head->next指向空，链表翻转完成。新链表的头结点是tail。

画图帮助理解：
1 2 3 4 5
p<-q o
p<-q

时间复杂度

空间复杂度：总共递归n层，系统栈的空间复杂度是$O(n^2)$，总共需要额外$O(n^2)$的空间。

时间复杂度：链表中每个结点只被遍历一次，$O(n^2)$

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next)//空指针或只有一个点，直接返回
            return head;
        //否则，链表至少有两个点
        ListNode* tail=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return tail;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head||!head->next)//空指针或只有一个点，直接返回
            return head;
        auto p=head,q=p->next;
        while(q){
            auto o=q->next;
            q->next=p;//q指向p
            p=q,q=o;//右移
        }
        head->next=NULL;//head变成新的尾结点
        return p;//p是新的头结点
    }
};

方法2

链表，迭代

将所有结点的next指针指向前驱节点。

但是单链表在迭代时不能直接找到前驱节点，需要一个额外的指针来保存前驱节点。在改变当前节点的next指针前，注意保存它的后继节点。

时间复杂度

空间复杂度：遍历时只有三个额外变量，故额外的空间复杂度是$O(1)$
时间复杂度：只遍历一次链表，$O(n)$

C++ 代码

class Solution{
    public:
    ListNode* reverseList(ListNode* head){
        ListNode* prev=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* next=cur->next;
            cur->next=prev;
            prev=cur,cur=next;//右移
        }
        return prev;
    }
};