회전 목록 Leetcode 솔루션  


난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 블룸버그 게시물에서 페이스북 서비스 링크드 인 Microsoft 삼성
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 연결된 목록 두 포인터

문제 회전 목록 Leetcode 솔루션은 연결 목록과 정수를 제공합니다. 연결 리스트를 오른쪽으로 k만큼 회전시키라는 지시를 받았습니다. 따라서 연결 목록을 오른쪽으로 k만큼 회전하면 각 단계에서 목록에서 마지막 요소를 가져와서 위치에 배치합니다. 우리 반복 k개의 이러한 작업을 수행할 때까지 이 작업을 수행합니다. 몇 가지 예를 살펴보겠습니다.

head = [1,2,3,4,5], k = 2
[4,5,1,2,3]

설명 : 작업을 2 개의 간단한 회전 작업으로 나누겠습니다. 따라서 첫 번째 단계 또는 이동에서 목록 끝에서 요소를 가져 와서 앞에 배치합니다. 따라서 목록은 [5, 1, 2, 3, 4]가됩니다. 이제 다시 동일한 작업을 반복하여 목록 [4, 5, 1, 2, 3]을 만듭니다. 따라서 답입니다.

head = [0,1,2], k = 4
[2, 0, 1]

설명 : 프로세스를 4 번 반복하면 응답 링크 목록이 생성됩니다. 아래 이미지를 보면 더 잘 이해할 수 있습니다.

회전 목록 Leetcode 솔루션

회전 목록 Leetcode 솔루션에 대한 접근 방식  

문제 회전 목록 Leetcode 솔루션은 회전을 위한 정수가 있는 연결 목록이 제공된다고 말합니다. 이것은 목록을 오른쪽으로 k 자리 회전해야 함을 의미합니다. 목록의 끝에서 요소를 가져와 앞에 배치하는 간단한 작업으로 문제를 이해할 수 있습니다. 방법이 없기 때문에 효율적으로 끝에서 요소를 제거하고 앞에 놓습니다. 우리는 작업을 수행하는 다른 방법을 생각할 필요가 있습니다. 관찰하면 k 연산을 수행한 후 끝에서 k 요소가 제거되고 앞에 배치되는 것을 볼 수 있습니다. 여기서 주의할 점은 k의 크기가 의 크기보다 크면 연결 목록. 우리는 길이에 대해 k의 모듈로를 취할 것입니다. 연결 목록.

참조
이진 검색 트리에서 최소값을 가진 노드 찾기

완료되면 끝에서 k 번째 노드. 그런 다음 일부 작업을 수행하고 마지막 노드의 다음 노드를 헤드에 할당합니다. 끝에서 k번째 노드를 연결 목록의 헤드로 할당합니다. 그러나 끝에서 k-1 번째 노드의 다음 노드를 null로 할당하는 것을 잊어서는 안됩니다. 이제 이 3가지 작업을 수행한 후 목록을 회전했습니다.

회전 목록 Leetcode 솔루션 용 코드  

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
    int data;
    ListNode* next;
};

ListNode* rotateRight(ListNode* head, int k) {
    if(head==NULL || head->next==NULL)return head;

    ListNode *tmp = head;
    int cnt = 0;
    while(tmp)tmp=tmp->next,cnt++;
    tmp=head;
    k%=cnt;
    if(k==0)return head;

    while(k--)tmp = tmp->next;
    ListNode *tmpHead = head;
    while(tmp->next!=NULL){
        tmp = tmp->next;
        head = head->next;
    }
    ListNode* newHead = head->next;
    tmp->next = tmpHead;
    head->next = NULL;
    return newHead;
}

int main(){
    ListNode *head = new ListNode();
    head->data = 0;
    head->next = new ListNode();
    head->next->data = 1;
    head->next->next = new ListNode();
    head->next->next->data = 2;

    head = rotateRight(head, 4);
    while(head != NULL){
        cout<<head->data<<" ";
        head = head->next;
    }
}
2 0 1

자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class ListNode{
  int data;
  ListNode next;
}

class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null)return head;
    
        ListNode tmp = head;
        int cnt = 0;
        while(tmp != null){
            tmp=tmp.next;
            cnt++;
        }
        tmp=head;
        k %= cnt;
        if(k==0)return head;

        while(k-- > 0)
            tmp = tmp.next;
        ListNode tmpHead = head;
        while(tmp.next != null){
            tmp = tmp.next;
            head = head.next;
        }
        ListNode newHead = head.next;
        tmp.next = tmpHead;
        head.next = null;
        return newHead;
    }
    
    public static void main(String[] args){
    	ListNode head = new ListNode();
      head.data = 0;
      head.next = new ListNode();
      head.next.data = 1;
      head.next.next = new ListNode();
      head.next.next.data = 2;
  
      head = rotateRight(head, 4);
      while(head != null){
          System.out.print(head.data + " ");
          head = head.next;
      }
    }
}
2 0 1

복잡성 분석  

시간 복잡성

의 위에), 여기서 N은 연결 목록의 크기를 나타냅니다. 연결 목록을 탐색해야하므로 시간 복잡도는 선형이며 목록의 크기에 따라 달라집니다.

참조
Isomorphic Strings Leetcode 솔루션

공간 복잡성

O (1), 각 노드에 대한 정보를 저장할 필요가 없기 때문입니다. 따라서 공간 복잡성은 일정합니다.

1