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

/**
 * 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;
        } pPre;

    }
};

使用递归的方式进行反转，递归反转链表代码太简洁和优雅了，但是要注意基线条件，不能无限循环,使用递归的核心：不要跳到递归里去！
        if(head == nullptr || head->next == nullptr)
             head;
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = last;
    }
};

:
    ListNode* reverseBetween(ListNode* head,int m,1)">int n) {
        按照题意，时间复杂度为O(n)
        可以使用迭代和递归两种方式进行，时间复杂度都是O(n)，但是递归的空间复杂度为O(n)，而迭代为O(1)
        
        递归解法
        if(m == 1)
             reverseN(head,n);
        head->next = reverseBetween(head->next,m-1,n-);
         head;  
    }
    ListNode* successor = nullptr;
    ListNode* reverseN(ListNode* head,1)"> n)
    {
        if(n==)
        {
            successor = head->next;
             head;
        }
        ListNode* last = reverseN(head->next,1)">);
        head->next->next = successor;
         last;
    }

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

};

*
 * 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) {}
 * };
 :
    ListNode* reverseKGroup(ListNode* head,1)"> k) {
        先反转以head开头的k个元素
        将第k+1个元素作为head递归调用reverseKGroup函数
        将上述两个过程的结果连接起来
        base case 如果最后的元素不足k个，就保持不变
         nullptr;
        ListNode* a = head;
        ListNode* b = head;
        0;i<k;i++)
        {
            if(b == nullptr)
                 head;
            b = b->next;
        }
        ListNode* newHead = reverse(a,b);
        a->next = reverseKGroup(b,k);
         newHead;
    }
    ListNode* reverse(ListNode* a,ListNode* b)
    {
        ListNode* pCur = a;
        ListNode* pPre = b)
        {
            pNext = pCur-> pPre;

    }
};