##题目
上一篇文章咱们解决了如何反转整个链表的问题
那么如何反转一个链表的一部分节点呢?
比如我们要反转下边这个链表的3~7范围的节点
我们可以把这个链表分成三个部分了
其中1~2和8是不需要做任何操作的
只有3~7部分的链表需要被反转,而整个链表的反转我们已经知道怎么做了
反转3~7部分的链表之后,只需要让2->7、3->8就能解决这个题目了
在这个过程中,只需要记录几个关键的节点就行了
即:
第一部分链表的起始节点(1节点)
第一部分链表的结尾节点(2节点)
第二部分链表的起始节点(3节点)
第二部分链表的结尾节点(7节点)
第三部分链表的起始节点(8节点)
考虑到指定的反转范围可能是从第一个节点开始的
我们需要先定义一个“-1”节点
令“-1”节点的next指向链表的起始节点
然后按照解题思路就能顺利解题了
结合“必会算法:反转链表Ⅰ”中定义的节点,我们可以定义以下几个节点来标记关键节点
第一部分链表的起始节点:”-1“节点的next节点
第一部分链表的结尾节点:pointerEnd指向的节点
第二部分链表的起始节点:head指向的节点
第二部分链表的结尾节点:pre指向的节点
第三部分链表的起始节点:next指向的节点
初始位置如下图
根据给定需要反转的起始位置
通过遍历链表,可将pointerEnd节点指向2
pre和head节点指向3,即需要反转链表的起始位置
然后定义cur和next节点
接下来的操作就是反转第二部分整个链表
直到pre指向要求反转链表的截止位置,第七个节点
此时已完成节点的反转,并且关键节点都有标记
令
pointerEnd.next = pre
head.next = cur
返回”-1“节点的next就可以了
##代码实现
public static Node reverseRangeLinkedList(Node head, int start, int end)
{
if (head == null || head.next == null)
{ return head;
}
Node pointer = new Node(-1, head);
Node pre = pointer;
Node pointerEnd = pre;
for (int i = 0; i < start; i++)
{
pointerEnd = pre;
pre = pre.next;
}
head = pre;
Node cur = pre.next;
Node next = cur;
pre.next = null;
while (next != null && start < end)
{
next = next.next;
cur.next = pre;
pre = cur;
cur = next;
start++;
}
pointerEnd.next = pre;
head.next = cur;
return pointer.next;
}
算法时间复杂度O(end),end为要求反转范围的截止位置
算法空间复杂度O(1)
测试一下
public static void main(String[] args) {
Node head = new Node(1);
Node temp = head;
for (int i = 2; i < 10; i++) {
temp.next = new Node(i);
temp = temp.next;
}
int start = 3;
int end = 8;
System.out.println(head + "::反转::" + reverseRangeLinkedList(head, start, end));
}
文/戴先生@2021年11月20日