[Leetcode] 61. Rotate List

문제 : https://leetcode.com/problems/rotate-list/

---

linked-list 의 head 노드가 주어지면 오른쪽으로 k만큼 회전한 뒤의 linked-list의 head를 반환하라.

---

입력으로 주어진 링크드 리스트를 한 번 탐색하면서 전체 길이를 구한다. (let, cnt)

만약 오른쪽으로 cnt번 회전하면 원래의 링크드 리스트와 동일해지므로, 나머지 연산을 한 k % cnt 만큼만 오른쪽 회전시키면 된다.

링크드 리스트를 다시 한 번 탐색하면서 

 

o -> o -> o -> o -> o

만일 위와 같은 링크드 리스트가 있고 k가 2라면 빨간색 노드가 새로운 헤드 노드가 될 것이다. 즉, head노드의 cnt - k번째 next 노드가 헤드노드가 된다. 회전한 뒤의 모습은 원래 링크드 리스트의 가장 마지막 노드의 next에 원래의 head 노드를 연결하고(1), 새로운 head 노드의 이전 노드의 next 연결은 끊어준다(2).

o -> o -(1)-> o -> o -> o -> null (2)

 

시간복잡도는 N을 linked-list 길이라 했을 때, O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/61.%20Rotate%20List.cpp