Leetcode 매일 한 문제: 25. K 개 반전 링크

1829 단어
체인 시 계 를 드 리 겠 습 니 다. k 개의 노드 마다 한 조 를 뒤 집 습 니 다. 뒤 집 힌 체인 시 계 를 되 돌려 주 십시오.
k 는 정수 로 링크 의 길이 보다 작 거나 같 습 니 다.
만약 에 노드 총수 가 k 의 정수 배가 아니라면 마지막 에 남 은 노드 를 원래 의 순서 로 유지 하 십시오.
예시:
이 링크 지정: 1 - > 2 - > 3 - > 4 - > 5
k = 2 시, 돌아 와 야 합 니 다: 2 - > 1 - > 4 - > 3 - > 5
k = 3 시, 돌아 와 야 합 니 다: 3 - > 2 - > 1 - > 4 - > 5
설명:
    당신 의 알고리즘 은 상수 의 추가 공간 만 사용 할 수 있 습 니 다.    너 는 단순히 노드 내부 의 값 을 바 꾸 는 것 이 아니 라 실제 적 으로 노드 교환 을 해 야 한다.
처음에 생각 한 스 택 작업 은 제목 의 요구 가 상수 공간 복잡 도 만 있 기 때문에 노드 를 바 꾸 는 방법 으로 구체 적 으로 구역 을 나 누 어 반전 을 하 는 것 이다. 반전 과정 에서 반드시 점 과 점 간 의 관 계 를 파악 하고 방향 을 정리 하면 된다.
/**
 * 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) {
        ListNode a = new ListNode(0);
        a.next = head;
        ListNode b = a;
        ListNode right = a;  //          
        while(right.next != null){   //          
            for(int i = 0;i < k && right!=null;i++){  //        
                right = right.next;
            }
            if(right == null){  //    
                break;
            }
            ListNode next = right.next; //        
            ListNode left = b.next; //           
            for(int i = 0;i < k;i++){  //      , left    next  ,    left next  
                ListNode per = left.next;  
                left.next = next;
                next = left;
                left = per;
            }
            b.next = next;  //      next
            for(int i = 0;i < k;i++){
                b = b.next;  //       
            }
            right = b;   //  right   b  
        }
        return a.next;
    }
}

좋은 웹페이지 즐겨찾기