牛客网高频算法题系列-BM2-链表内指定区间反转
题目形容
将一个节点数为 size 链表 m 地位到 n 地位之间的区间反转,要求工夫复杂度 O(n),空间复杂度 O(1)。
原题目见:BM2 链表内指定区间反转
解法一:链表遍历,指针替换
因为起始地位可能是头结点,所以首先设置一个虚构的头结点dummyNode并将next指向原有的头结点,而后处理过程如下:
- 首先遍历链表,找到起始地位m的前一个结点pre,用来记录反转前的结点;
- 而后用cur和next记录pre的next结点,用next记录cur的next结点;
- 而后持续遍历链表,通过替换pre、next、cur的next指针,将next结点转到pre结点的下一个结点处,而后循环解决cur的下一个结点;
- 遍历到完结完结地位n的结点即反转完结。
- 最初,返回dummyNode结点的next结点即为反转后的链表。
public class Bm002 {
/**
* @param head ListNode类
* @param m 起始地位
* @param n 完结地位
* @return ListNode类
*/
public static ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null) {
return head;
}
if (m == n) {
return head;
}
// 设置虚构头结点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
// pre为反转区间的前一个结点
ListNode pre = dummyNode;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
// cur初始为反转区间的起始结点
ListNode cur = pre.next;
ListNode next;
for (int i = 0; i < n - m; i++) {
// 通过替换next指针指向,将next结点转到pre结点的下一个结点处
next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
// 最初,返回dummyNode结点的next结点即为反转后的链表
return dummyNode.next;
}
public static void main(String[] args) {
ListNode head = ListNode.testCase2();
System.out.println("指定区间反转之前");
ListNode.print(head);
ListNode newHead = reverseBetween(head, 2, 4);
System.out.println("指定区间反转之后");
ListNode.print(newHead);
}
}
$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量!