猿辅导：单列表反转

1. 一个单向链表，逆序 index 在 [i，j] 之间的节点，返回逆序后的链表，index 是 zero-based
比如： A -> B -> C -> D -> E, i = 1, j = 3
返回结果： A -> D -> C -> B -> E

比如： 比如： A -> B -> C -> D -> E, i = 1, j = 10
返回结果： A -> E -> D -> C -> B

public class Main {

    static class Node {
        char val;
        Node next;

        Node(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Node A = new Node(‘A‘);
        Node B = new Node(‘B‘);
        Node C = new Node(‘C‘);
        Node D = new Node(‘D‘);
        Node E = new Node(‘E‘);
        A.next = B;
        B.next = C;
        C.next = D;
        D.next = E;
        Node head = getNeedReversedList(A, 1, 10);
        while (head != null) {
            System.out.print(head.val);
            head = head.next;
        }
    }

    public static Node getNeedReversedList(Node head, int i, int j) {
        Node temp = head;// 用于遍历的node
        Node fh = head;// head
        Node ft = null;// 指向i-1的Node
        Node si = null;// 指向i的Node
        Node sj = null;// 指向j的Node
        Node th = null;// 指向j+1的Node
        int index = 0;
        while (temp != null) {
            if (i > 0 && index == i - 1) {
                ft = temp;
            }
            if (index == i) {
                si = temp;
            }
            if ((temp.next == null && index < j) || index == j) {
                sj = temp;
            }
            if (index > j) {
                th = temp;
            }
            temp = temp.next;
            index++;
        }
        si = reversedList(si, sj);
        temp = si;
        while (temp != null) {
            if (temp.next == null) {
                sj = temp;
            }
            temp = temp.next;
        }
        ft.next = si;
        sj.next = th;
        return fh;
    }

    public static Node reversedList(Node head, Node tail) {
        tail.next = null;// 设置原来尾节点的next为null
        Node newhead = null;// 保存返回的逆序的list
        Node pre = null;
        Node cur = head;// 用于遍历需要逆序的list
        while (cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        newhead = pre;
        return newhead;
    }
}