Leetcode Study Day 30

Rotate List

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

My solution

My solution is firstly use an unordered_map to store the index and the related nodes. Then I calculate the rotated link is start from which node. The I link the nodes again with the rotated index order.

/**
 * 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 || k == 0) return head;
        int count = 0;
        unordered_map <int, ListNode*> listMap;
        ListNode* current = head;
        while (current){
            count += 1;
            listMap[count] = current;
            current = current -> next;
        }
        if (k%count == 0){
            return head;
        }
        int start = count + 1 - k % count;
        int new_count = start;
        ListNode* new_head = listMap[new_count];
        ListNode* new_current = new_head;
        new_count += 1;
        while( new_count != start){
            if (new_count > count){
                new_count = 1;
            }
            new_current -> next = listMap[new_count];
            new_current = new_current -> next;
            new_count += 1;
        }
        new_current -> next = nullptr;
        return new_head;
    }
};

One thing to notice is that I need to update the last node’s next to nullptr. Otherwise, it will cause a cycle in the linked list.

Improved solution from Leetcode

I found a more easy and elegant idea. In this solution, it first count the length of the link list first, then link the tail node to the head node.
Then, it will find the new head node by calculating the new head index. Finally, it will update the tail node’s next to nullptr.

In this solution, compard to mine, it doesn’t need one extra map to store index and nodes.

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return null;
        int listNum = 1;
        ListNode tail = head;
        
        //find tail and count listNum
        while(tail.next != null){
            listNum++;
            tail = tail.next;
        }
        tail.next = head;
        int newHeadIndex = listNum - k % listNum;

        for(int i = 0; i < newHeadIndex; i++){
            tail = tail.next;
        }
        
        head = tail.next;
        tail.next = null;

        return head;
    }
}