链表OJ（三） 反转链表合集

目录

反转链表

反转链表 II

链表中的节点每k个一组翻转

---

描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤10000≤n≤1000

要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

示例1

输入：{1,2,3}返回值：{3,2,1}

【解法一】迭代

class Solution {
public:ListNode* ReverseList(ListNode* pHead) {if(pHead==nullptr)return nullptr;ListNode* cur = pHead, *prev = nullptr, *Next = nullptr;while(cur){Next = cur->next;cur->next = prev;prev = cur;cur = Next;}return prev;}
};

【 解法二】递归

 

 92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

 思路：将需要反转的链表从中间抽取出来，记录好取出来链表的前一个（用于后续的链接），然后将需要反转部位进行反转即可，最终Next指针指向了5的位置，将新反转的链表遍历到最后一个进行链接即可

① 创建一个新的头结点，利用这个新的头结点找到cur前一个的位置，用prev来保存

 ② 对cur开始进行反转，就是反转链表上面那个题

 反转结束就是上图，把图形转换一下

 ③ 然后将c_p链表接在 前半部分prev与后半部分cur之间就行

class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {if(head==nullptr || left==right)return head;ListNode* newhead = new ListNode(0);newhead->next = head;ListNode* cur = head;ListNode* prev = newhead, *Next = nullptr;for(int i = 0; i < left-1; i++){cur = cur->next;    // 找到prev位置prev = prev->next;    // 找到开始反转位置}ListNode* cur_pre = nullptr;for(int i = left; i < right+1; i++){Next = cur->next;cur->next = cur_pre;    // 进行反转cur_pre = cur;cur = Next;}    prev->next = cur_pre;    // 将头接入链表while(cur_pre->next){cur_pre = cur_pre->next;    // 找到cp的尾部}cur_pre->next = Next;    // 尾部接入链表return newhead->next;    // 注意返回新头结点的next}
};

链表中的节点每k个一组翻转

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围：  0≤n≤2000 0≤n≤2000 ， 1≤k≤20001≤k≤2000 ，链表中每个元素都满足 0≤val≤10000≤val≤1000
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如：

给定的链表是 1→2→3→4→51→2→3→4→5

对于 k=2k=2 , 你应该返回 2→1→4→3→52→1→4→3→5

对于 k=3k=3 , 你应该返回 3→2→1→4→53→2→1→4→5

 首先遍历到第k个位置的元素，那么tail就到了下一组元素的起始位置。

然后进行从头反转，刚才的tail也可以为cur的反转提供最终判断条件

最后pre到达了3的位置，tail处于下一组元素的位置，head仍然在头结点1的位置，然后

head->next = reverseGroup（tail,  k） tail下一组的新的头结点。

class Solution {
public:/*** * @param head ListNode类 * @param k int整型 * @return ListNode类*/ListNode* reverseKGroup(ListNode* head, int k) {// write code hereListNode* tail = head;for(int i = 0; i < k; i++){if(tail == nullptr)    // tail不断往后遍历，最终位置就是第k个的下一个return head;        // 也就是下一组的起点tail = tail->next;    // 如果中间遇到nullptr直接返回head；不足k个}ListNode* pre = nullptr;ListNode* cur = head;while(cur != tail){ListNode* temp = cur->next;    // 进行反转cur->next = pre;pre = cur;cur = temp;}head->next = reverseKGroup(tail, k); // 注意这步return pre;                          // 理解head的位置}
};