剑指24：反转链表

传送门

nowcoder
leetcode

题目描述

输入一个链表，反转链表后，输出新链表的表头。

C++ 代码 - nowcoder

/*
    头插法，新建一个虚拟头节点
*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) return pHead;

        ListNode *dummy = new ListNode(-1), *p = pHead;
        dummy->next = nullptr;
        while (p != nullptr) {
            ListNode* q = p;
            p = p->next;
            q->next = dummy->next;
            dummy->next = q;
        }
        return dummy->next;
    }
};

/*
    三个指针
*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) return pHead;

        ListNode *prev = nullptr, *cur = head, *next = nullptr;
        while (cur != nullptr) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

C++ 代码 - leetcode

/*
    三个指针
*/
class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode *prev = nullptr, *cur = head, *next = nullptr;
        while (cur != nullptr) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

/*
	递归实现
*/
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* last = reverseList(head->next);
        head->next->next= head;
        head->next = nullptr;
        return last;
    }
};