반전 체인 테이블과 그룹 반전 체인 테이블

1. 체인 시계 반전

고전적인 반전 체인 시계, 먼저 코드

public class ListNode {

    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
    }
}

public class PrintList {

    public static void print(ListNode root) {
        while (root != null) {
            System.out.print(root.data + " ");
            root = root.next;
        }
        System.out.println();
    }
}

public class Reverse {

    public ListNode init() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        n1.next = n2;
        n2.next = n3;
        return n1;
    }

    public ListNode reverse(ListNode root) {
        if (root == null || root.next == null) {
            return root;
        }

        ListNode pre = null, cur = root;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }


    public static void main(String[] args) {
        Reverse obj = new Reverse();
        ListNode root = obj.init();
        ListNode result = obj.reverse(root);
        PrintList.print(result);
    }
}

주요 단계는 다음과 같습니다.현재 노드의next 노드를 tmp 노드로 저장합니다.2. 현재 노드의next 노드를pre 노드로 설정합니다(반전 실현).3. pre 노드를 현재 노드로 설정합니다.4. 현재 노드를 첫 번째 단계로 저장하는 tmp 노드로 설정합니다.

2. 그룹 반전 체인 테이블

하나의 체인 테이블을 정하고 각 k개의 노드가 한 조로 반전시킨다. k는 정정수이고 그 값은 체인 테이블의 길이보다 작거나 같다.만약 노드의 총수가 k의 정수배가 되지 않는다면, 마지막 남은 노드는 원래의 순서를 유지할 것이다.
예를 들어 체인 테이블이 1->2->3->4->5k=2일 경우, 반전 후의 결과는 2->1->4->3->5k=3일 경우, 반전 후의 결과는 3->2->1->4->5
문제 풀이의 사고방식은 다음과 같이 추상화할 수 있다.루트로 시작하는 k 요소를 먼저 반전합니다.2. 제k+1개의 요소를head귀속으로reverseKGroup 함수(즉 반전 함수)를 호출한다.위 두 과정의 결과를 연결하다.

public class ReverseKs {

    public ListNode init() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        return n1;
    }

    public ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null, cur = a;
        while (cur != b) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }

        return pre;
    }

    public ListNode reverseKGroup(ListNode root, int k) {
        if (root == null) return null;
        ListNode a = root, b = root;
        for(int i=0; i