Problem.java

package demo;

/**
 * @author Francis
 * @date 2020/6/17
 */
public class Main {

  static class Node{
    int val;
    Node next;

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

    @Override
    public String toString() {
      StringBuilder sb = new StringBuilder();
      Node tmp = next;
      sb.append(val);

      while (tmp != null) {
        sb.append("->");
        sb.append(tmp.val);
        tmp = tmp.next;
      }
      return sb.toString();
    }
  }

  public static void main(String[] args) {
    Node head = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    Node node5 = new Node(5);
    Node node6 = new Node(6);
    Node node7 = new Node(7);
    Node node8 = new Node(8);

    head.next =  node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;
    node6.next = node7;
    node7.next = node8;

    Node res = resolve(head, 3);

    System.out.println(res);
  }

  public static Node resolve(Node head, int k) {
    if (k == 1) {
      return reverse(head);
    }
    Node newHead;
    if (head.next != null) {
      newHead = resolve(head.next, k);
    } else {
      return head;
    }
    head.next = newHead;

    Node p = head;
    int count = 1;
    Node nextSeg = null;
    Node lastNode = null;
    while (p.next != null) {
      count++;
      p = p.next;
      if (count == k) {
        nextSeg = p.next;
        lastNode = p;
      }
    }
    int mod = count % k;
    if (mod > 0) {
      return head;
    } else {
      lastNode.next = null;
      newHead = reverse(head);
      head.next = nextSeg;
      return newHead;
    }
  }

  private static Node reverse(Node head) {
    if (head.next == null) {
      return head;
    }
    Node newHead = reverse(head.next);
    Node p = newHead;
    while (p.next != null) {
      p = p.next;
    }
    head.next = null;
    p.next = head;
    return newHead;
  }
}