剑指Offer_24_反转链表

❗️LeetCode_206_反转链表

题目描述：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点

示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制：0 <= 节点个数 <= 5000

链表节点定义如下：
struct ListNode {

    int m_nKey;
    ListNode* m_pNext;
};

解法1：循环

ListNode* ReverseList(ListNode* pHead)
{
    ListNode* pReversedHead = nullptr;  //反转后的链表头节点
    ListNode* pNode = pHead;  //pNode初始化时指向头节点
    ListNode* pPrev = nullptr;
  
    while(pNode != nullptr) {
      
        //通过后面的代码可以看到节点1、节点2之间的指针断了，所以需要有一个指针提前保存节点2
        ListNode* pNext = pNode->m_pNext;

        if(pNext == nullptr)
            pReversedHead = pNode;

        pNode->m_pNext = pPrev;  //这一行代码极容易理解错，pNode的下一个节点指向的是一个空节点，注意区分‘pPrev = pNode->m_pNext;’

        //NULL <- 1  2 -> 3 -> 4 -> 5 -> NULL
        pPrev = pNode;  //pPrev指向节点1
        pNode = pNext;  //pNode指向节点2
    }

    return pReversedHead;
}

解法2：递归

/**
 * 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 == NULL || head->next == NULL) {
            return head;
        }

        //递归实现
        ListNode* newHead = reverseList(head->next);  //递归到最里层的时候：newHead此时指向5

        //递归到最里层的时候：head此时指向4，head->next指4->5，head->next->next = head指5->4
        head->next->next = head;  

        head->next = NULL;  //4指向NULL

        return newHead;
    }
};