题目

链表定义：

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

题解

1. 迭代法（双指针）

实际上是三个指针，一个指向当前节点之前pre，一个指向当前节点cur，还有一个tmp用于暂存下个节点，防止断链后找不到下个节点，代码如下

  • 时间复杂度$O(n)$
  • 空间复杂度$O(1)$
class Solution {//两个方法。1.迭代
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre = nullptr, *cur = head;
        while(cur){
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

2. 递归法

基本思想是先通过递归直到递归到只剩一个节点，此时直接返回本节点。从导数第二个节点开始，让当前节点的下个节点指向自己，然后自己指向空。相当于完成了后面链表的翻转，然后再返回当前节点的头节点，不断重复直到整个链表重新排列

  • 时间复杂度$O(n)$
  • 空间复杂度$O(n)$
class Solution {//两个方法。2. 递归
public:
    ListNode* reverseList(ListNode* head) {
        //第一句包含两种情况。
        //1.链表为空，直接返回
        //2.链表只有一个节点，或递归到最后一个节点，返回当前节点
        if(!head || !head->next) return head;
        //tmp存已经翻转过来的后面的链表的头节点
        auto tmp = reverseList(head->next);
        //head是当前节点，这一句的作用是让当前节点的原始下一节点指向自己，然后自己再指向空
        //此时head的上一节点还是指向自己，跳出本层递归后处理上一节点
        head->next->next = head;
        head->next = nullptr;
        head = tmp;
        return head;//返回上层递归村的后半链表的头节点
    }
};