福州网站设计外包,公司网站做的比较好,wordpress isadmin,房天下搜房网官网目录
反转链表
反转链表 II
链表中的节点每k个一组翻转 描述 给定一个单链表的头结点pHead(该头节点是有值的#xff0c;比如在下图#xff0c;它的val是1)#xff0c;长度为n#xff0c;反转该链表后#xff0c;返回新链表的表头。 数据范围#xff1a; 0≤n≤10000≤…目录
反转链表
反转链表 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(pHeadnullptr)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(headnullptr || leftright)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 right1; 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 对于 k2k2 , 你应该返回 2→1→4→3→52→1→4→3→5 对于 k3k3 , 你应该返回 3→2→1→4→53→2→1→4→5 首先遍历到第k个位置的元素那么tail就到了下一组元素的起始位置。
然后进行从头反转刚才的tail也可以为cur的反转提供最终判断条件
最后pre到达了3的位置tail处于下一组元素的位置head仍然在头结点1的位置然后
head-next reverseGrouptail, 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的位置}
};
