[LeetCode] 61. Rotate List - 문제풀이

Description

주어진 링크드리스트를 k만큼 오른쪽으로 로테이션하여 반환하는 문제입니다.

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

Solution 1. Two pointers

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    ListNode dHead = new ListNode(0);
    dHead.next = head;
    ListNode fast = dHead, slow = dHead;

    int len = 0;
    while (fast.next != null) {
        fast = fast.next; //Get the total length
        len++;
    }

    k = k % len;
    int i = len-k;
    while(i > 0){ //Get the len-k th node
        slow = slow.next;
        i--;
    }

    fast.next = dHead.next; //Do the rotation
    dHead.next = slow.next;
    slow.next = null;

    return dHead.next;
    
}

두개의 포인터를 이용하여 fast는 리스트의 맨끝에 위치시켜 길이를 구하고 하나는 로테이션 시작지점으로 새로운헤드의 이전노드(len-k)까지 위치시켜 준뒤 맨마지막노드(fast)에 기존 첫번째 노드를 연결해주고 로테이션 되는 첫번재 노드를 반환해줍니다.

• 시간복잡도 : O(N)+@
• 공간복잡도 : O(1)

Solution 2. Using List

public ListNode rotateRight(ListNode head, int k) {

    List<ListNode> nodeList = new ArrayList<>();
    while (head != null){
        nodeList.add(head);
        head = head.next;
    }
    int len = nodeList.size();
    k = k % len;
    if(len == 1 || k==0 ) return nodeList.get(0);

    ListNode newHead = nodeList.get(len-k);
    nodeList.get(len-1).next = nodeList.get(0);
    nodeList.get(len-k-1).next = null;

    return newHead;
}

원하는 위치의 노드에 바로 접근 할 수 있도록 List에 순서대로 노드를 담아 줘서 처리하는 방법입니다. 공간복잡도는 늘어나나 시간복잡도를 줄일 수 있습니다.

• 시간복잡도 : O(N)
• 공간복잡도 : O(N)

Reference

Rotate List - LeetCode