首页 算法 链表

# 题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

206. 反转链表 - 力扣（LeetCode）

# 分析

可以选择重新再定义一个链表，然后一个个 next。但这样有点浪费空间。

# 双指针法

既然是反转，那么我们只需要把指向全部调转即可。定义两个指针，cur 和 pre，用 cur 指针指向头节点，pre 指针赋值 null，把 cur.next 用 temp 保存，然后 cur.next 指向 pre，然后相互赋值重复逻辑完成反转。

// 时间复杂度: O (n)
// 空间复杂度: O (1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存 cur 的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur 的下一个节点，因为接下来要改变 cur->next
            cur->next = pre; // 翻转操作
            // 更新 pre 和 cur 指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

# 递归法

// 时间复杂度: O (n), 要递归处理链表的每个节点
// 空间复杂度: O (n), 递归调用了 n 层栈空间
class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }
};

      

          
          
      

  


   


    

  
    
      
    
    更新于