反转部分单向链表

题目

给定一个单向链表的头节点 head，以及两个整数 from 和 to，在单向链表上把第 from 个节点到第 to 个节点这一部分进行反转。

例如

1-＞2-＞3-＞4-＞5-＞null, from=2, to=4
调整结果为：1-＞4-＞3-＞2-＞5-＞null
1-＞2-＞3-＞null, from=1, to=3
调整结果为：3-＞2-＞1-＞null

要求

1. 如果链表长度为 N，时间复杂度要求为 O(N)，额外空间复杂度要求为 O(1)。
2. 如果不满足 1 <= from <= to <= N，则不用调整。

解答

这里主要要注意 from 是否为第一个节点，即是否为头节点的问题。

代码

public class Node {
    public int value;
    public Node next;

    public Node(int value) {
        this.value = value;
    }
}

public Node reversePart(Node head, int from, int to) {
    int len = 0;
    Node node1 = head;
    Node fPre = null;
    Node tPos = null;
    /**
        * 遍历链表，找到 from 的前一个节点
        * 和 to 的后一个节点
        */
    while (node1 != null) {
        len++;
        fPre = len == from - 1 ? node1 : fPre;
        tPos = len == to + 1 ? node1 : tPos;
        node1 = node1.next;
    }
    if (from > to || from < 1 || to > len) { // 输入不合理，注意，from = 1 和 to = len 是合法的情况
        return head;
    }
    // 下面进行反转
    node1 = fPre == null ? head : fPre.next; // 如果 fPre 等于 null，则说明 from = 1，否则直接将 fPre 的下一个节点赋给 node1
    Node node2 = node1.next; // 保存 node1.next
    node1.next = tPos; // 先将部分链表的头节点给转了，所以下面不需要再处理将反转好的 “部分链表” 的尾部给接到 tPos 的操作了
    Node next = null;
    while (node2 != tPos) {
        next = node2.next; // 保存下一个节点
        node2.next = node1;
        node1 = node2;
        node2 = next;
    } // node1 是最后一个 “部分链表” 的最后一个节点
    if (fPre != null) { // 如果 fPre 不是 null，即 from != 1
        fPre.next = node1; // 直接接上就好
        return head;
    }
    return node1; // 这是 from 为头节点的情况
}