61. Rotate List

소스 코드는 여기 있습니다.
문제는 여기 있습니다.

Problem

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 * 10^9

Solution

연결 리스트의 head가 주어질 때 오른쪽으로 k만큼 회전시킨 리스트를 구하는 문제입니다.

import io.lcalmsky.leetcode.ListNode;

public class Solution {

  public ListNode rotateRight(ListNode head, int k) {
    if (head == null) {
      return null;
    }
    ListNode current = head;
    int size = 1;
    while (current.next != null) { // (1)
      size++;
      current = current.next;
    }
    current.next = head; // (2)
    current = head; // (3) 
    int rotate = size - k % size; // (4)
    while (rotate-- > 1) { // (5)
      current = current.next;
    }
    ListNode result = current.next; // (6)
    current.next = null; // (7) 
    return result;
  }
}

1. 리스트의 길이를 구합니다.
2. current가 현재 마지막 노드이므로 다음 노드를 head로 설정합니다.
3. 마지막 노드도 head 노드로 설정합니다.
4. 실제 회전시켜야 할 횟수를 구합니다. 오른쪽 방향으로 회전시킬 것이므로 전체 길이에서 k를 길이로 나눈 나머지만큼 빼주면 됩니다.
5. rotate 횟수만큼 current 노드를 다음 노드로 이동합니다.
6. 3번에서 current 노드를 dummy로 설정하였기 때문에 그 다음 노드부터 반환해야 합니다.
7. 마지막 노드의 다음 노드와의 연결을 끊어줍니다.

ListNode.java 전체 보기

package io.lcalmsky.leetcode;

import java.util.Objects;

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public static ListNode of(int... integers) {
        if (integers == null || integers.length == 0) throw new IllegalArgumentException();

        ListNode head = new ListNode(0);
        ListNode last = head;
        ListNode p;
        for (int integer : integers) {
            p = new ListNode(integer);
            last.next = p;
            last = last.next;
        }

        return head.next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof ListNode)) return false;
        ListNode listNode = (ListNode) o;
        return val == listNode.val &&
                Objects.equals(next, listNode.next);
    }

    @Override
    public int hashCode() {
        return Objects.hash(val, next);
    }
}

Test

package io.lcalmsky.leetcode.rotate_list;

import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;

import io.lcalmsky.leetcode.ListNode;
import org.junit.jupiter.api.Test;

class SolutionTest {

  @Test
  void testAll() {
    assertAll(
        () -> test(ListNode.of(1, 2, 3, 4, 5), 2, ListNode.of(4, 5, 1, 2, 3)),
        () -> test(ListNode.of(0, 1, 2), 4, ListNode.of(2, 0, 1))
    );
  }

  private void test(ListNode head, int k, ListNode expected) {
    // when
    Solution solution = new Solution();
    ListNode actual = solution.rotateRight(head, k);
    // then
    assertEquals(expected, actual);
  }
}