剑指offer - 反转链表

题目

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

链表结点定义

struct ListNode {
    int m_nKey;
    ListNode m_pNext;
};

分析

为了正确的反转一个链表，需要调整链表中指针的方向。为了分析使用下图来理解

20180606084512110.png

图中所示的链表中，h，i，和j是3个相邻的结点。假设经过若干操作，我们已经把结点h之前的指针调整完毕，这些结点的m_pNext都指向前一个结点。接下来我们把结点i的m_pNext指向结点h，此时的链表结构如图所示。可以看到，由于结点i的m_pNext指向了它的前一个结点，导致我们无法在链表中遍历到结点j。为了避免链表在结点i处断开，我们需要在结点i的m_pNext修改之前，把结点j保存下来

也就是说，在调整结点i的m_pNext指针时，除了需要知道结点i本身，还需要知道i的前一个结点h。同时，还需要事先保结点i的下一个结点j，以防止链表断开。因此，相应地，我们需要定义3个指针，分别指向当前遍历到的结点、它的前一个结点以及后一个结点

最后是反转链表的头结点，它是原始链表的尾结点，尾结点的m_pNext为nullptr.

实现

#include <iostream>
using namespace std;

struct ListNode {
    int m_nKey;
    ListNode *m_pNext;
};

ListNode *ReverseList(ListNode *pHead)
{
    // 反转之后的头结点
    ListNode *pReversedHead = nullptr;
    // 当前结点
    ListNode *pNode = pHead;
    // 前一个结点
    ListNode *pPrev = nullptr;

    // 遍历链表
    while (pNode != nullptr) {
        // 当前结点的下一个结点
        ListNode *pNext = pNode->m_pNext;

        // 下一个结点为空，那么当前结点为尾结点
        if (pNext == nullptr)
            pReversedHead = pNext; // 将尾结点设置为头结点用于返回

        // 下一个结点存在,将上一个结点作为下结点
        pNode->m_pNext = pPrev;

        // 将当前结点记录为上一个结点
        pPrev = pNode;

        // 下一个结点作为当前结点
        pNode = pNext;
    }

    return pReversedHead;
}

递归实现

递归的方法其实是非常巧的，它利用递归走到链表的末端，然后再更新每一个结点的next值 ，实现链表的反转

ListNode* ReverseList(ListNode *pHead) {
    //如果链表为空或者链表中只有一个元素
    if(pHead == NULL || pHead->next == NULL) return pHead;
    //先反转后面的链表，走到链表的末端结点
    ListNode* pReverseNode=ReverseList(pHead->next);
    //再将当前节点设置为后面节点的后续节点
    pHead->next->next = pHead;
    pHead->next=NULL;

    return pReverseNode;
}

头结点插入法

从原链表的头部一个一个取节点并插入到新链表的头部

ListNode* ReverseList(ListNode *pHead) {
    if (pHead == NULL) return NULL;
    ListNode* head = pHead;
    pHead = pHead->next;
    head->next = NULL;
    while (pHead) {
        ListNode *next = pHead->next;
        pHead->next = head;
        head = pHead;
        pHead = next;
    }
    return head;
}

使用栈来实现反转

遍历原链表入栈，再遍历栈构造反向链表

ListNode* ReverseList(ListNode *pHead) {
    if (pHead == NULL || pHead->next == NULL) return pHead;

    ListNode *p = pHead;
    ListNode *newHead;
    stack<ListNode *> stack1;
    // 入栈
    while(p->next != NULL) {
        stack1.push(p);
        p=p->next;
    }
    // 尾结点作为新的头结点
    newHead = p;
    // 出栈
    while(!stack1.empty())
    {
        p->next = stack1.top();
        p = p->next;
        stack1.pop();
    }
    p->next = NULL;
    return newHead;
}

参考

《剑指offer》
反转链表