反转部分单向链表

【题目】 给定一个单向链表的头节点 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，则不用调整。

本题有可能存在换头的问题，比如题目的第二个例子，所以函数应该返回调整后的新头节点，整个处理过程如下： 1．先判断是否满足 1≤from≤to≤N，如果不满足，则直接返回原来的头节点。 2．找到第 from-1 个节点 fPre 和第 to+1 个节点 tPos。fPre 就是要反转部分的前一个节点，tPos 是反转部分的后一个节点。把反转的部分先反转，然后正确地连接 fPre 和 tPos。

例如：1->2->3->4->null，假设 fPre 为节点 1，tPos 为节点 4，要反转部分为 2->3。先反转成3->2，然后 fPre 连向节点 3，节点 2 连向 tPos，就变成了 1->3->2->4->null。 3．如果 fPre 为 null，说明反转部分是包含头节点的，则返回新的头节点，也就是没反转之前反转部分的最后一个节点，也是反转之后反转部分的第一个节点；如果 fPre 不为 null，则返回旧的头节点。 全部过程请参看如下代码中的 reversePart 方法。

public class ReversePart {

    class Node {
        private int value;
        private Node next;
        public Node(int data) {
            this.value = data;
        }
    }

    public Node reversePart(Node head, int from, int to) {
        Node node1 = head;
        // fPre指向要反转的
        Node fPre = null;
        Node tPos = null;
        int n = 0;

        // 遍历链表，找出fPre节点和tPos节点，并得到链表长度
        while (node1 != null) {
            n++;
            fPre = n == from - 1 ? node1 : fPre;
            tPos = n == to + 1 ? node1 : tPos;
            node1 = node1.next;
        }
        if (from > to || from < 1 || to > n) {
            return head;
        }

        /**
         * 解释：
         * 使node1指向需要反转的第一个节点
         * 如果fPre为null，那么fPre的next属性就没有值，所以这里使用三目运算
         */
        node1 = fPre == null ? head : fPre.next;
        // node2指向node1后面一个节点
        Node node2 = node1.next;

        // 反转第一个需要反转的节点，使node1的next指针指向tPos
        node1.next = tPos;

        // 申请一个变量用于保存当前node2的next指针所指向的位置
        Node next = null;
        // 开始反转剩余部分节点
        while (node2 != tPos) {
            // next指向node2的next指针所指向的位置
            next = node2.next;
            // 反转node2，使node2的next属性指向前一个节点。这样node2的next属性就丢失了，所以要用next变量保存
            node2.next = node1;

            // node1、node2节点向后移
            node1 = node2;
            node2 = next;
        }

        // 如果fPre不为空表示，反转部分在链表中间，所以不需要换头，直接返回旧头节点即可
        if (fPre != null) {
            // 使fPre指向反转之后反转部分的第一个节点
            fPre.next = node1;
            return head;
        } else {
            // 如果fPre为空，那么反转之后反转部分的第一个节点就是头节点
            return node1;
        }
    }
}