C++의 정렬 및 회전 연결 목록에서 회전 계산

<시간/>

우리는 연결 리스트를 받았습니다. 목록이 먼저 정렬된 다음 K개의 노드만큼 회전됩니다. 목표는 K의 값을 찾는 것입니다. 아래 링크드 리스트가 K개의 노드만큼 회전하는 입력으로 주어지면 -

그렇다면 원본은 -

C++의 정렬 및 회전 연결 목록에서 회전 계산

그리고 여기에서 K가 2임을 알 수 있습니다. 입력 연결 목록은 원래 정렬된 연결 목록에서 2개 노드의 회전입니다.

예를 들어 이해합시다.

입력 − 목록 :5 → 7 → 9 → 1 → 3

출력

연결 목록의 요소는 다음과 같습니다. 5 7 9 1 3

정렬 및 회전 연결 목록의 회전 수는 - 3입니다.

설명 − 원래의 정렬된 목록에서 3회전 후에 입력 목록을 얻을 수 있습니다.

1 → 3 → 5 → 7 → 9, 원본9 → 1 → 3 → 5 → 7, 회전 17 → 9 → 1 → 3 → 5, 회전 25 → 7 → 9 → 1 → 3 회전

입력 − 목록 − 17 → 25 → 62 → 99

출력

연결 목록의 요소는 − 17 25 62 99

입니다.

정렬 및 회전 연결 목록의 회전 수는 - 4입니다.

설명 − 원래의 정렬된 목록에서 4회전 후에 입력 목록을 얻을 수 있습니다.

<예비>17 → 25 → 62 → 99, original99 → 17 → 25 → 62, 회전 162 → 99 → 17 → 25, 회전 225 → 62 → 99 → 17, 회전 317 → 25 → 62 → 99, 회전 4

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

입력 연결 목록에는 다음 노드가 이전 노드보다 작은 한 지점이 있습니다. 입력 문자열도 정렬되면 원래 문자열의 전체 회전입니다. 헤드 노드에서 시작하여 (현재 노드의 데이터> 헤드 노드의 데이터)까지 순회하고 카운트를 증가시킵니다. (현재 노드의 데이터 <헤드 노드의 데이터)가 루프를 끊는 경우. 카운트는 입력 목록을 얻기 위해 원래 목록에서 여러 번 회전합니다.

입력 목록을 가져 와서 그 안에 요소를 삽입하십시오.
insert_node(struct List_Node** head, int data) 함수는 데이터가 있는 단일 연결 목록의 헤드에 노드를 삽입합니다.
함수 print(struct List_Node* node)는 while 루프를 사용하여 헤드에서 끝까지 입력 연결 목록을 인쇄합니다.
회전 함수(struct List_Node* head)는 연결 목록의 헤드 포인터를 가져오고 원래 연결 목록에서 수행된 회전 수를 반환하여 입력 연결 목록을 가져옵니다.
초기 카운트를 0으로 합니다.
temp 변수를 헤드 노드의 데이터 부분으로 사용합니다.
while 루프를 사용하여 연결 목록의 끝에 도달할 때까지 탐색합니다. (머리!=NULL).
모든 현재 노드의 데이터가 temp보다 큰 경우 카운트를 증가시킵니다.
현재 노드의 데이터가 헤드 노드의 데이터( temp)보다 작은 경우. 휴식,
회전 수를 계산합니다.
결과로 카운트를 반환합니다.

예시

#include 네임스페이스 std;struct List_Node{ int data; struct List_Node* next;};int 회전(struct List_Node* head){ int count =0; int temp =헤드 -> 데이터; while (head !=NULL){ if (temp>
 head->data){ break; } 카운트++; 머리 =머리 -> 다음; } 반환 카운트;}void insert_node(struct List_Node** 헤드, int 데이터){ struct List_Node* new_node =new List_Node; new_node->data =데이터; new_node->next =(*head); (*head) =new_node;}void print(struct List_Node* 노드){ while (노드 !=NULL){ cout<<노드->데이터<<" "; 노드 =노드->다음; }}int main(){ 구조체 List_Node* 헤드 =NULL; insert_node(&head, 2); insert_node(&head, 1); insert_node(&head, 18); insert_node(&head, 35); insert_node(&head, 28); cout<<"연결된 목록의 요소는 다음과 같습니다. "; 인쇄(머리); cout<<"\n정렬 및 회전 연결 목록의 회전 수는 다음과 같습니다. "< 출력
 
 위의 코드를 실행하면 다음 출력이 생성됩니다 -
 연결 목록의 요소:28 35 18 1 2정렬 및 회전 연결 목록의 회전 수:2