.leetcode(61. Rotate List)

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

 

1. 2022/05/08 시도

소요시간: 12분

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) {
            return null;
        }

        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }
        if (length == 1) {
            return head;
        }
        
        int remain = k%length;
        if (remain == 0) {
            return head;
        }

        ListNode prev = head;
        for (int i=0; i<length-remain-1; i++) {
            prev = prev.next;
        }
        ListNode newNode = prev.next;
        prev.next = null;
        ListNode newHead = newNode;
        while (newNode.next != null) {
            newNode = newNode.next;
        }
        newNode.next = head;
        
        return newHead;
    }
}

풀이 접근 과정

먼저 길이를 구한다. k번 로테이션이 길이 이하만큼만 될 수 있게 하기 위해서이다.

그다음에 while문으로 새로 시작하는 노드를 찾는다. 이때 이전노드를 찾아야 제대로 끊을 수 있기때문에 -1만큼 로테이션해준다.

찾았다면 기존노드의 마무리를 null로 바꿔주고 해당노드를 신규헤드로 지정한다. 신규헤드의 끝에서 기존 head노드를 연결해준다.

전체적으로 edge케이스를 확이하여 조건문을 달아준다.

 

느낀점

• 링크드리스트 문제는 풀 수록 edge케이스 문제라는 생각이 든다. 풀다보면 길이구하기, 사이클 구하기 등등 여러 유형이 있는데 가장 어려운 부분은 edge케이스를 잘 피할 수 있느냐의 문제다.
• 이번 풀이는 한번도 틀리지 않고 통과한데 의의가 있다. leetcode의 medium문제들은 함정들이 있기 마련인거 같다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형