目录
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return null;
}
// cur用于记录当前节点的指向,刚开始就是指向head
ListNode cur = head;
// prev用于记录 前一段未反转的部分 的最后一个节点,默认初始指向null
ListNode prev = null;
// 反转链表后的头结点
ListNode tail = null;
// 用于记录表反转之后的最后一个节点
ListNode reverseTail = null;
// 先获取prev,遍历结束后cur指向的是 待反转链表部分 的起使位置
for (int i = 1; i < m; i++) {
prev = cur;
cur = cur.next;
}
// 待反转链表部分 的起使位置也就是链表反转之后的最后一个节点,我们先记录下来,为了最后和 后一段未反转部分 连接起来
reverseTail = cur;
// 开始反转链表,遍历次数要是n-m+1,这样才能反转全,那么此时cur指向的就是 后一段未反转部分 的起始位置
for (int i = 0; i < n-m+1; i++) {
ListNode next = cur.next;
cur.next = tail;
tail = cur;
cur = next;
}
// 现在将 待反转链表部分 的尾节点与 后一段未反转部分 的起始节点连接起来
reverseTail.next = cur;
// 判断 前一段未反转的部分 的最后一个节点是否为空,如果为空的话,说明反转的是该链表前n个节点,直接返回 反转链后的头结点
if (prev == null) {
return tail;
} else {
// 否则的话,将 前一段未反转的部分 的最后一个节点与 待反转链表部分 的头节点连接起来,然后返回head
prev.next = tail;
return head;
}
}
}
时间复杂度:\(O(N)\)
空间复杂度:\(O(1)\)
我们可以递归实现反转链表
然后难度再加深一点,实现反转前 n 个链表
但是题目需求是还有前 m-1 个链表节点不需要反转,所以我们通过递归把前 m-1 个个省略跳过即可(递归时候m和n都要同时减1,这样才能保证反转的部分保持不变),当 m 减少为1时,反转前n个即可
在 reverseN 中,我们需要一个tail来记录后一部分不反转链表的第一个节点,也是反转链表最后一个节点指向的地方:head.next = tail;
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// m为1代表就是直接反转前n个节点
if (m == 1) {
return reverseN(head, n);
}
head.next = reverseBetween(head.next, m-1, n-1);
return head;
}
/**
* 用于记录反转链表部分的尾结点指向
*/
ListNode tail = null;
/**
* 反转链表的前n个节点
*/
public ListNode reverseN(ListNode head, int n) {
if (n == 1) {
tail = head.next;
return head;
}
ListNode p = reverseN(head.next, n-1);
head.next.next = head;
head.next = tail;
return p;
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章