206. 反转链表

力扣

https://leetcode.cn/problems/reverse-linked-list/description/?favorite=2cktkvj

题解

1.递推或迭代

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
            return head;
        ListNode *p=nullptr;
        ListNode *q = head,*t = nullptr;
        while(q){
            t=q->next;
            q->next = p;
            p=q;
            q=t;
        }
        return p;
    }
};

2.递归

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head|| !head->next)
            return head;
        ListNode *new_head = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    }
};