class Solution {

  public static void main(String[] args) {
    ListNode node = new ListNode(
      1,
      new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5))))
    );
    System.out.println("原链表：" + node);
    // System.out.println("反转后的链表：" + reverseList(node));
    // System.out.println("0-2反转结果：" + reverseList(node,2));
    // System.out.println("2-4反转结果：" + reverseList(node,2,4));
  }

  // 从left节点开始到right节点反转
  public static ListNode reverseList(ListNode head, int left, int right) {
    if (null == head || null == head.next) {
      return head;
    }
    int num = right - left + 1;
    if (num < 1) {
      return head;
    }
    // 定义一个虚头
    ListNode xHead = new ListNode(0, head);
    ListNode leftNode = xHead;
    for (int i = left; i > 1; i--) {
      leftNode = leftNode.next;
    }
    leftNode.next = reverseList(leftNode.next, num);
    return xHead.next;
  }

  // 从开始反转num个节点
  public static ListNode reverseList(ListNode head, int num) {
    if (num == 1 || null == head || null == head.next) {
      return head;
    }
    ListNode tail = head.next;
    ListNode cur = reverseList(head.next, num - 1);
    head.next = tail.next;
    tail.next = head;
    return cur;
  }

  // 链表反转
  public static ListNode reverseList(ListNode head) {
    if (null == head || null == head.next) {
      return head;
    }
    // 后面节点反转后的尾节点
    ListNode tail = head.next;
    ListNode cur = reverseList(head.next);
    head.next = tail.next;
    tail.next = head;
    return cur;
  }

  public static class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    @Override
    public String toString() {
        ListNode node = this;
        StringBuffer buffer = new StringBuffer();
        while(null != node){
            buffer.append(node.val);
            buffer.append(">");
            node = node.next;
        }
        return buffer.substring(0,buffer.length()-1).toString();
    }
  }
}