公众号:offer多多
V1
2022/04/23阅读:14主题:橙心
【Daily LeetCoding Challenge14】 K 个一组翻转链表
【Daily LeetCoding Challengeday14】 K 个一组翻转链表
大家好,我是小王
为了不别人KO,话不多说,直接干货

前言
据说 这是字节 面试题,单链表 你会翻转 需要3个指针,
-
主要观察区别,phead 每组翻转完毕后 需要重置 -
phead 从哪里来呢 链表 无法倒序 ,需要ppre 记录 pcur前面一个位置。

思路

-
K 个一组翻转链表
//init: myeahd(phead||ppre)->1(pcur)--2--3--4--5
//initmyeahd-->2 -1(phead||ppre) --3(pcur) -4 -5
-
最关键地方:k组翻转完毕后,忘记重置 3. for 循环 死循环 写多少次 每次都都有小错误
-

最关键地方:k组翻转完毕后,需要重置
时间复杂度
-
o(n)
代码
-
剑指 Offer 24. 反转链表 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) {
ListNode* phead = NULL; //无固定头节点的单链表。转后链表的头节点
ListNode* pnext = NULL; // 防止迷路
ListNode* pcur = head;
//链表适中在head插入
while (pcur)
{
pnext = pcur->next; // 1--2
pcur->next = phead; //1->NULL
phead = pcur; //phead->1--null;
pcur = pnext;// move like ++
}
return phead;
}
};
-
单链表翻转go

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
//三路指针
var phead *ListNode
var pnext *ListNode
var pcur *ListNode
phead = nil
pnext = nil
pcur = head
// 遍历 翻转
for pcur != nil {
pnext = pcur.Next
pcur.Next = phead //这里是指针 非固定节点,不需要phead.NEXT
phead =pcur //这里是指针 非固定节点,不需要phead.NEXT 一直在变化
pcur = pnext //迭代
}
return phead
}
25. K 个一组翻转链表 c++
/**
* 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) {
//单链表翻转 翻转全部元素,这里翻转k个 区别是什么?
//单链表翻转是 一个old 链表 构造 一个新的链表 其实 2个链表
// k 必须 部分翻转。原地翻转
// K <= n
//If the number of nodes is not a multiple of k then left-out nodes,
//in the end, should remain as it is.
if (nullptr == head || nullptr == head->next || k <= 0 ) return head;
//01 k个一组,最后不翻转
ListNode* ptemp = head;
int count = 0;
while(ptemp)
{
ptemp = ptemp->next;
count++;
}
//02 定义遍历
ListNode myhead(-1,head);
//三路指针第一次初始化
ListNode* phead = &myhead;
ListNode* pcur = head;
ListNode* ppre = &myhead;
//03 顺序遍历 k组翻转一次 然后初始化三路指针
for (int group = count/k;group > 0 ;group--){
//每次翻转k元素
for(int i = 0;i <k ;i++)
{
if (phead->next == pcur){
ppre = pcur;
pcur = pcur->next;
}else {
ppre->next =pcur->next;
pcur->next = phead->next;
phead->next =pcur;
pcur =ppre->next;//move
}
}
//翻转第二组时候,需要重置phead位置
if( pcur) {
phead = ppre; // 单链表翻转 phead 第一位置,这里不是 区别!!!每组的第一个位置
}
}
return myhead.next;
}
};

如何学习
一、这个技术出现的背景、初衷和要达到什么样的目标或是要解决什么样的问题
二、这个技术的优势和劣势分别是什么
三、这个技术适用的场景。任何技术都有其适用的场景,离开了这个场景
四、技术的组成部分和关键点。
五、技术的底层原理和关键实现

六、已有的实现和它之间的对比
作者介绍
公众号:offer多多
V1