61. Rotate List

61. Rotate List

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next or k == 0:  # 예외 처리: 리스트가 비었거나 노드가 하나인 경우
            return head

        # 1. 리스트 길이 계산
        length = 1
        last = head
        while last.next:
            last = last.next
            length += 1

        # 2. k를 리스트 길이로 나눈 나머지로 축소
        k = k % length
        if k == 0:  # k가 0이면 회전할 필요가 없음
            return head

        # 3. 새로운 head를 찾기 위해 (length - k - 1)번째 노드 탐색
        """
        -1 하는 이유는 
        첫번째 노드부터 시작해서, 점프할 개수를 찾기때문에, 1이 포함,         
        다시 말해서,
        새로운 tail이 새로운 head 바로 직전 노드를 정확히 가리키도록 조정.
        """
        new_tail_pos = length - k - 1
        new_tail = head
        for _ in range(new_tail_pos):
            new_tail = new_tail.next

        new_head = new_tail.next
        last.next = head
        new_tail.next = None
        return new_head

 

 

https://youtu.be/UcGtPs2LE_c?si=JlnyKk0jiYedutjk

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head
        
        # Get length
        length, tail = 1, head
        while tail.next:
            tail = tail.next
            length += 1
        
        k = k% length
        if k == 0: 
            return head
        
        # Move to the pivot and rotate
        cur = head
        for i in range(length - k - 1):
            cur = cur.next
        
        newHead = cur.next
        cur.next = None
        tail.next = head

        return newHead