免费下载简历模板网站,国家公示企业信息查询系统,仿站网,logo在线设计软件视频地址
反转链表【基础算法精讲 06】_哔哩哔哩_bilibili
概念
链表的每一个结点都包含节点值 和1指向下一个结点的next指针 , 链表的最后一个结点指向空; 206 . 反转链表
用cur记录当前遍历到的结点 #xff0c; 用pre表示下一个结点 #xff0c; 用nxt表示cur的下一个…视频地址
反转链表【基础算法精讲 06】_哔哩哔哩_bilibili
概念
链表的每一个结点都包含节点值 和1指向下一个结点的next指针 , 链表的最后一个结点指向空; 206 . 反转链表
用cur记录当前遍历到的结点 用pre表示下一个结点 用nxt表示cur的下一个结点先将cur-next修改成pre,然后把pre 更新 成cur ,cur 更新 成nxt ;
代码如下 :
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre nullptr;ListNode* cur head ;while(cur ! nullptr){ListNode* nxt cur-next ;cur-next pre ;pre cur ;cur nxt;}return pre ;}
};
92 . 反转链表II
这一题只需要反转[l,r]的部分结点 将反转链表的前一个结点成为p0 ;
然后和上一题一样反转链表 ;
也就是 : 把p0的next指针指向cur,p0指向pre 有一个特殊的情况当l 1 的时候 没有p0 , 可以在前面加上一个哨兵结点为p0 ; 代码如下 :
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dmy new ListNode(0,head) ;ListNode* p0 dmy ;for(int i0;ileft-1;i){p0 p0 - next ;}ListNode* pre nullptr ;ListNode* cur p0-next ;for(int i1;iright-left1;i){ListNode* nxt cur-next ;cur-next pre ;pre cur ;cur nxt ;}p0-next-next cur ;p0-next pre ;return dmy-next ;}
};
25 . 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) {int n 0 ;ListNode* cur head ;while(cur!nullptr){ // 拿到链表的长度 n;cur cur-next ;}ListNode* dmy new ListNode(0,head) ;ListNode* p0 dmy ;while(nk){n-k;ListNode* pre nullptr;ListNode* cur p0-next ;for(int i0;ik;i){ListNode* nxt cur-next;cur-next pre ;pre cur ;cur nxt ;}ListNode* tmp p0-next ;p0-next-next cur ;p0-next pre ;p0 tmp ;}return dmy - next;}
};
