【C++】“反转链表”相关的题目

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

（1）这道题是经典的题目了，用迭代的方式解决也是很容易的，代码量也不大。分享一个我个人做题的方式，我会先在题目开头写注释，理清我结题的思路，然后写代码就很容易了。

/**
 * 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 == nullptr || head->next == nullptr)
            return head;
        ListNode* pPre = nullptr;
        ListNode* pCur = head;
        ListNode* pNext = nullptr;
        while(pCur != nullptr)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }return pPre;

    }
};

（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 == nullptr || head->next == nullptr)
            return head;
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

2.反转链表II:

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

（1）递归，空间换时间，我佛了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //按照题意，时间复杂度为O(n)
        //可以使用迭代和递归两种方式进行，时间复杂度都是O(n)，但是递归的空间复杂度为O(n)，而迭代为O(1)

        //递归解法
        if(m == 1)
            return reverseN(head, n);
        head->next = reverseBetween(head->next, m-1, n-1);
        return head;
    }
    ListNode* successor = nullptr;
    ListNode* reverseN(ListNode* head, int n)
    {
        if(n==1)
        {
            successor = head->next;
            return head;
        }
        ListNode* last = reverseN(head->next, n-1);
        head->next->next = head;
        head->next = successor;
        return last;
    }

（2）迭代实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        //按照题意，时间复杂度为O(n)
        //可以使用迭代和递归两种方式进行，时间复杂度都是O(n)，但是递归的空间复杂度为O(n)，而迭代为O(1)

        //迭代解法
        ListNode* pCur = head;
        ListNode* pPre = nullptr;
        ListNode* pNext = nullptr;
        ListNode* pPreM = nullptr;
        ListNode* pM = nullptr;
        for(int i=0;i<m-1;i++)
        {
            pPreM = pCur;
            pCur = pCur->next;
        }
        pM = pCur;
        for(int j=m;j<=n;j++)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        if(m != 1)
        {
            pPreM->next = pPre;
        }
        pM->next = pNext;
        return m==1? pPre : head;
    }

};

 3.K个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //先反转以head开头的k个元素
        //将第k+1个元素作为head递归调用reverseKGroup函数
        //将上述两个过程的结果连接起来
        //base case 如果最后的元素不足k个，就保持不变
        if(head == nullptr)
            return nullptr;
        ListNode* a = head;
        ListNode* b = head;
        for(int i=0;i<k;i++)
        {
            if(b == nullptr)
                return head;
            b = b->next;
        }
        ListNode* newHead = reverse(a,b);
        a->next = reverseKGroup(b,k);
        return newHead;
    }
    ListNode* reverse(ListNode* a, ListNode* b)
    {
        ListNode* pCur = a;
        ListNode* pPre = nullptr;
        ListNode* pNext = nullptr;
        while(pCur != b)
        {
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
        return pPre;

    }
};