题目链接

牛客网

题目描述

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

输入：
{1,2,3}
输出：
{3,2,1}

解题思路

递归

使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // 递归结束条件
        if(pHead==nullptr||pHead->next==nullptr)
            return pHead;
        // 递归获取后n-1个反转，返回反转后的头结点
        ListNode* ret = ReverseList(pHead->next);
        // 当前头结点的下一个结点指向当前头结点
        // eg: 1->2->NULL ==> NULL<-1<-2
        pHead->next->next = pHead;
        // 当前头结点指向NULL
        pHead->next = NULL;
        return ret;
    }
};

• 时间复杂度 O(N) ： 遍历链表使用线性大小时间。
• 空间复杂度 O(N)： 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。

  迭代

使用头插法。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr)
            return pHead;
        ListNode* ret = new ListNode(-1);
        while(pHead){
            // 保存下一个结点
            ListNode* tmp = pHead->next;
            // 将当前结点用头插法插入ret
            pHead->next = ret->next;
            ret->next = pHead;
            // 移到下一个结点
            pHead = tmp;
        }
        return ret->next;
    }
};

• 时间复杂度 O(N)
• 空间复杂度 O(N)

双指针（一）

• 定义两个指针： pre 和 cur ；pre 在前 cur 在后。
• 每次让 pre 的 next 指向 cur ，实现一次局部反转
• 局部反转完成之后， pre 和 cur 同时往前移动一个位置
• 循环上述过程，直至 pre 到达链表尾部

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr)
            return pHead;
        ListNode *cur =NULL,*pre = pHead,*tmp = NULL;
        while(pre){
            tmp = pre->next;
            pre->next = cur;
            cur = pre;
            pre = tmp;
        }
        return cur;
    }
};

双指针（二）

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr)
            return pHead;
        ListNode *cur =pHead,*tmp;
        while(pHead->next!=NULL){
            // 记录下次head指向
            tmp = pHead->next->next;
            // 当前cur转变指向
            pHead->next->next = cur;
            // 向前移动cur
            cur = pHead->next;
            // head指向cur下一个
            pHead->next = tmp;
        }
        return cur;
    }
};