연결된 목록이 있다고 가정합니다. 목록을 올바른 k 위치로 회전해야 합니다. k 값은 음수가 아닙니다. 따라서 목록이 [1,23,4,5,NULL]이고 k =2이면 출력은 [4,5,1,2,3,NULL]
이 됩니다.단계를 살펴보겠습니다 -
- 목록이 비어 있으면 null을 반환합니다.
- len :=1
- tail :=head라는 노드 하나 생성
- 테일의 다음이 null이 아닌 동안
- len 1씩 증가
- 꼬리:=꼬리의 다음
- 꼬리 다음:=머리
- k :=k 모드 렌
- newHead :=null
- for i :=0 ~ len – k
- 꼬리:=꼬리의 다음
- newHead :=꼬리의 다음
- 꼬리 다음:=null
- newHead 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int data){ val = data; next = NULL; } }; ListNode *make_list(vector<int> v){ ListNode *head = new ListNode(v[0]); for(int i = 1; i<v.size(); i++){ ListNode *ptr = head; while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr->next){ cout << ptr->val << ", "; ptr = ptr->next; } cout << "]" << endl; } class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if(!head) return head; int len = 1; ListNode* tail = head; while(tail->next){ len++; tail = tail->next; } tail->next = head; k %= len; ListNode* newHead = NULL; for(int i = 0; i < len - k; i++){ tail = tail->next; } newHead = tail->next; tail->next = NULL; return newHead; } }; main(){ Solution ob; vector<int> v = {1,2,3,4,5,6,7,8,9}; ListNode *head = make_list(v); print_list(ob.rotateRight(head, 4)); }
입력
[1,2,3,4,5,6,7,8,9] 4
출력
[6, 7, 8, 9, 1, 2, 3, 4, ]