题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
#test02 链表内指定区间反转
重点：头插法（保证链表第一个节点不乱跑，稳定整条链）、找到m位置、区间内反转，注意返回值
还是太菜，但是算法题很上头
/*
* 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 here
//m等于n 不需要翻转
if (m === n) {
return head;
}
//链表为空或链表长度为1不需要翻转
if (head == null || head.next == null) {
return head;
}
//定义一个新表头指向head 头插法！
let newHead = new ListNode(-1);
newHead.next = head;
//先遍历找到m的位置,
let pre = newHead;
for (let i = 1; i < m; i++) {
pre = pre.next;
}
//找到m的位置:pre(翻转链表，这里pre相当于 m-n链 表头位置)，从m开始翻转到n
let p1 = pre.next, p2;
for (let i = m; i < n; i++) {
p2 = p1.next;
p1.next = p2.next;
p2.next = pre.next;
pre.next = p2;
}
//翻转完毕，返回的newHead.next（因为newHead是相对前移一位的）
return newHead.next;
}
module.exports = {
reverseBetween: reverseBetween,
};
