Rotate List[Linked List,Two Pointers]

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

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

1. C

또 Naive하게 했다가 얻어 맞은 Time Limit ㅠㅠ

C는 빠른 언어라 상관 없을 줄 알았는데 얄짤 없네

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if(!head) return head;
    int cnt = 0;
    while(cnt!=k){
        cnt++;
        struct ListNode* curr = head;
        struct ListNode* prev = head;
        while(curr->next){
            prev = curr;
            curr = curr->next;
        }
        curr->next = head;
        prev->next = NULL;
        head = curr;
    }
    return head;
}

 

while문을 쓸 때마다 깨림직하다 ;;

그래서 꼼수를 부려보았다. 통과를 하긴 했다는 ㅎㅎ;;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if(!head) return head;
    int cnt1 = 0;
    struct ListNode* temp = head;
    while(temp){
        cnt1++;
        temp = temp->next;
    }
    int cnt2 = 0;
    int k2 = k%cnt1;
    while(cnt2!=k2){
        cnt2++;
        struct ListNode* curr = head;
        struct ListNode* prev = head;
        while(curr->next){
            prev = curr;
            curr = curr->next;
        }
        curr->next = head;
        prev->next = NULL;
        head = curr;
    }
    return head;
}

 

2. C++ 

정석적으로 풀어보았다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head||!head->next) return head;
        int len = 1;
        ListNode* temp = head;
        while(temp->next){
            temp=temp->next;
            len++;
        }
        k = k % len;
        if(k==0) return head;

        ListNode* curr = head;
        for(int i=0;i<len-k-1;i++){
            curr = curr->next;
        }
        ListNode* newhead = curr->next;
        curr->next = nullptr;
        temp->next = head;

        return newhead;
    }
};

 

3. Python

이번엔 재미좀있게 KHS님께서 좋아하시는 deque를 써봤다.

사실 뭐.. 굳이 안 써도 되지만 그냥 써 봄! 

# 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 : return head

        lst = deque()
        len = 1
        temp = head
        while temp.next :
            lst.append(temp)
            len +=1
            temp = temp.next
        lst.append(temp)
        k %= len
        if k == 0 : return head

        for i in range(k):
            newhead = lst.pop()
        newtail = lst.pop()
        
        temp.next = head
        newtail.next = None
        return newhead