LC 61 Rotate linked list

We need to rotate the linked list to the right by k

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

We can see that It is no different from partitioning the linked list into two group and swap the group’s position.

  1. We iterate through the linked list to find the end.

  2. Point the end of the linked list to the head

  3. We record the length of linked list

  4. If shifting is not a multiple of length, (k % len != 0), we will find the end of first group by progress from tail (len – (k % len)) nodes.

5.then the new head will be tail -> next

Potential bugs

Length of linked list

Since we are not using dummy head, the linked list starts with length 1.

    ListNode* rotateRight(ListNode* head, int k) {
        if (!head)
            return head;
        ListNode *newH, *newTail;
        newH = newTail = head;
        int length = 1;
        //first figure the length with n
        while(newTail -> next){
            newTail = newTail -> next;
            length ++;
        }
        //point end of second group to head
        newTail -> next = head;

        //find the end of first group, first group len is len - k
        //can skip if rotation doesn't change linked list
        if (k % length){
            for (int i = 0; i < length - (k % length); i ++){
                newTail = newTail -> next;
            }
        }
        newH = newTail -> next;
        newTail -> next = NULL;
        return newH;

    }

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax