수필 - 각 k 개 노드 반전 링크 (고 효율 해법)

제목: 하나의 체인 시 계 를 제시 하고 k 개의 노드 마다 한 조 를 뒤 집 으 며 뒤 집 힌 체인 시 계 를 되 돌려 줍 니 다.
k 는 정수 로 링크 의 길이 보다 작 거나 같 습 니 다.만약 에 노드 총수 가 k 의 정수 배가 아니라면 마지막 남 은 노드 를 원래 의 순서 로 유지 합 니 다.
예시:
이 링크 지정: 1 - > 2 - > 3 - > 4 - > 5
k = 2 시, 돌아 와 야 합 니 다: 2 - > 1 - > 4 - > 3 - > 5
k = 3 시, 돌아 와 야 합 니 다: 3 - > 2 - > 1 - > 4 - > 5
설명:
당신 의 알고리즘 은 상수 의 추가 공간 만 사용 할 수 있 습 니 다.너 는 단순히 노드 내부 의 값 을 바 꾸 는 것 이 아니 라 실제 적 으로 노드 교환 을 해 야 한다.
사고: 반전 함 수 를 따로 쓰 고 n% k = = 0 만 있 으 면 링크 가 반전 되 지 않 은 링크 의 결점 이 k 개 라 는 것 을 설명 한다. 그러면 반전 을 한다.또한 주의해 야 할 것 은 k 는 2 보다 크 고 반전 링크 가 의미 가 있다 는 것 이다.
코드 구현:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ListNode newTail=null;
    public void reverse(ListNode head,ListNode tail){
     //head    ，       ，         ，                 ，
     //      cur       ，     
        ListNode cur=head.next.next;//       
        ListNode curNext=cur.next;//        ，    
        while(cur!=null){
            //     cur curNext     ，while       true
            //  tail              ，cur        
            cur.next=head.next;//    
            head.next=cur;//     
            if(cur==tail){
                newTail.next=curNext;//           k           
                break;
            }
            cur=curNext;//          
            curNext=cur.next;
        }
        
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head==null||k<=1){
            return head;
        }
        ListNode newHead=new ListNode(-1);// k           
        newHead.next=head;
        ListNode tail=head;//         
        head=newHead;
        int n=1;
        while(tail!=null){
            if(n%k==0){
                newTail=newHead.next;//     
                reverse(newHead,tail);
                newHead=newTail;//               
                tail=newTail; 
            }
            tail=tail.next;
            n++;
        }
        return head.next;
    }
}