当前位置：首页 > ds >正文

牛客算法题目刷——链表总结

ds 2025/7/14 13:40:15

1.首先时反转链表，简单是简单，但总是写错！

	第一：总直接dummyNode.next赋值head，不可行呀，先指向的时null（pre)第二：循环内总是cur=cur.next，明明最开始记录了，此时这样写链表的cur指针已经变了

在这里插入图片描述

/** function ListNode(x){*   this.val = x;*   this.next = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/
function ReverseList( head ) {// write code herelet vHeadNode=new ListNode(0);let cur=head;while(cur){let next=cur.next;cur.next=vHeadNode.next;vHeadNode.next=cur;cur=next;}return vHeadNode.next;
}
module.exports = {ReverseList : ReverseList
};

2.在链表指定区间进行反转

	此题核心就是`找到区间的pre和next指针`，然后进行反转，最后连接链表找指针时条件，前一：m-,后一：cur.next

在这里插入图片描述

/** function ListNode(x){*   this.val = x;*   this.next = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/
function reverseBetween( head ,  m ,  n ) {// write code herelet vHeadNode=new ListNode(0);vHeadNode.next=head;let cur=vHeadNode;let leftPre,rightNext;//找leftPre&rightNext//分两半，left&待反转&右for(let i=0;i<n;i++){if(i===m-1)leftPre=cur;cur=cur.next;}rightNext=cur.next;//断开右部分cur.next=null;//核心let [start,end]=reverseList(leftPre.next);leftPre.next=start;end.next=rightNext;return vHeadNode.next;}
function reverseList(head){//返回链表前后节点!!!let vHead=new ListNode(0);let cur=head;while(cur){let next=cur.next;cur.next=vHead.next;vHead.next=cur;cur=next;}return [vHead.next,head]}
module.exports = {reverseBetween : reverseBetween
};

3. k个为一组进行反转(⭐⭐⭐）

此题较麻烦，思路就是先判断是否够k个不够直接返回结果，够的话先找到下一组的起始节点（上一组的结束首先赋值为dummy),记录下一组的起始节点bong断开后续链表，反转此组并返回新的起始节点，将此组链表和前后链表进行连接，并更新上一节点结束&cur当前节点。// 1. 检测剩余节点是否足够k个// 2. 切割当前分组并记录下一组起点// 3. 翻转当前分组// 4. 连接分组// 5. 移动指针准备处理下一组

特别注意指针，preEnd|cur|groupStart|groupEnd|nextGroupStart 为global指针

在这里插入图片描述

/** function ListNode(x){*   this.val = x;*   this.next = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @param k int整型* @return ListNode类*/
function reverseKGroup(head, k) {// write code hereconst dummy = new ListNode(-1); // 虚拟头节点简化操作dummy.next=head;//核心一个迁移链表的End和当前节点let prevGroupEnd = dummy; // 上一组的尾节点let current = head;while (current) {// 1. 检测剩余节点是否足够k个let groupStart = current;let groupEnd = prevGroupEnd;for (let i = 0; i < k; i++) {groupEnd = groupEnd.next;if (!groupEnd) return dummy.next; // 不足k个直接返回}// 2. 切割当前分组并记录下一组起点const nextGroup = groupEnd.next;groupEnd.next = null; // 切断当前分// 3. 翻转当前分组const [reversedHead, reversedTail] = reverseSubList(groupStart);// 4. 连接分组prevGroupEnd.next = reversedHead; // 连接上一组reversedTail.next = nextGroup; // 连接下一组// 5. 移动指针准备处理下一组prevGroupEnd = reversedTail;current = nextGroup;}return dummy.next;
}
//反思一下自己吧！！！简单但请仔细
function reverseSubList(head) {let dummyNode = new ListNode(0);let cur = head;while (cur) {let next = cur.next;cur.next = dummyNode.next;dummyNode.next = cur;cur = next;}return [dummyNode.next, head];
}
module