[자바 프로 그래 밍(온라인 필기시험)]두 개의 k 개 그룹 이 링크 를 뒤 집 는 문제(비 재 귀 와 재 귀 두 가지 해법 포함)

1.체인 시 계 를 하나 드 리 겠 습 니 다.k 노드 마다 한 조 를 뒤 집 습 니 다.뒤 집 힌 체인 시 계 를 되 돌려 주 십시오.만약 에 노드 총수 가 k 의 정수 배가 아니라면 마지막 에 남 은 노드 도 순 서 를 뒤 집 으 십시오.
1.비 귀속 해법

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null||k==1)return head;
        //  3   ，t   ，h        ，hh h    
        ListNode t=null,h=head,hh=head.next;
        int i=1;
        while(true){
            // i      
            h.next=t;
            if(i==k)break; //    k   ，    
            if(hh==null)break; //hh    h       ，          ，    
            i++;
            //     i+1   ，     
            t=h;
            h=hh;
            hh=hh.next;
        } 
        if(hh!=null)head.next=reverseKGroup(hh,k);
        return h;
    }

}

2.귀속 해법

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null||k==1)return head;
        //   k   
        ListNode kNode=head;
        for(int i=1;kNode!=null&&i<k;i++){
            kNode=kNode.next;
        }
        //   k+1   
        if(kNode!=null){
            kNode=kNode.next;
        }
        //   k   ，    k   
        ListNode res=reverse(head,k);
        if(kNode==null)head.next=null;
        else head.next=reverseKGroup(kNode,k);
        return res;
    }

    ListNode reverse(ListNode head, int k){
        if(head==null||head.next==null||k<=1)return head;
        ListNode res=reverse(head.next,k-1);
        head.next.next=head;
        head.next=null;
        return res;
    }
}

2.체인 시 계 를 하나 드 리 겠 습 니 다.k 개 노드 마다 한 조 를 뒤 집 습 니 다.뒤 집 힌 체인 시 계 를 되 돌려 주 십시오.만약 에 노드 총수 가 k 의 정수 배가 아니라면 마지막 에 남 은 노드 를 원래 의 순서 로 유지 하 십시오.
leetcode 문제 에 대응:25.K 개 반전 링크
1.비 귀속 해법

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null||k==1)return head;
        if(!hasKLength(head,k))return head;
        //  3   ，t   ，h        ，hh h    
        ListNode t=null,h=head,hh=head.next;
        int i=1;
        while(true){
            // i      
            h.next=t;
            if(i==k)break; //    k   ，    
            if(hh==null)break; //hh    h       ，          ，    
            i++;
            //     i+1   ，     
            t=h;
            h=hh;
            hh=hh.next;
        } 
        if(hh!=null)head.next=reverseKGroup(hh,k);
        return h;
    }

    boolean hasKLength(ListNode head, int k){
        for(int i=0;i<k;i++){
            if(head==null)return false;
            head=head.next;
        }
        return true;
    }
}

2.귀속 해법

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||head.next==null||k==1)return head;
        //   k   
        ListNode kNode=head;
        for(int i=1;kNode!=null&&i<k;i++){
            kNode=kNode.next;
        }
        //    k   ，         head
        if(kNode==null){
            return head;
        }
        //   k   ，    k   
        //   k+1       
        kNode=kNode.next;
        ListNode res=reverse(head,k);
        head.next=reverseKGroup(kNode,k);
        return res;
    }

    ListNode reverse(ListNode head, int k){
        if(head==null||head.next==null||k<=1)return head;
        ListNode res=reverse(head.next,k-1);
        head.next.next=head;
        head.next=null;
        return res;
    }
}
}

3.총화
비 재 귀 해법 의 난이 도 는 앞의 k 노드 를 수 동 으로 뒤 집 는 것 이다.재 귀 해법 의 난이 도 는'뒤 집기 전 k 개 노드'전에 k+1 개 노드 를 기록 하 는 것 이다.그렇지 않 으 면'앞의 k 개 노드'를 뒤 집 은 후에 k 개 노드 가 k-1 개 노드 를 가리 키 면 k+1 개 노드 를 잃 어 버 린 다.