61 Rotate List

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

impl Solution {
    pub fn rotate_right(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        
        let mut count = 0;
        let mut k_mut = k;
        let mut cursor = &head;
        loop {
            match cursor {
                Some(node) => {
                    cursor = &node.next;
                    count += 1;
                }, 
                None => {
                    break;
                }
            }
        }

        if count == 0 {
            return head
        }

        if k >= count {
            k_mut = k % count;
        }
        k_mut = count - k_mut;
        let mut temp = &mut head;
        while k_mut > 1 {
            match temp {
                Some(node) => {
                    temp = &mut node.next;
                    k_mut -= 1;
                }, 
                None => {
                    break;
                }
            }
        }
        let mut new_head = temp.as_mut().unwrap().next.take();
        temp.as_mut().unwrap().next = None;
        // need to append old head to end of new_head
        // find tail of new_head, then attach head
        let mut tail = &mut new_head;
        while let Some(node) = tail {
            if node.next.is_none() {
                node.next = head;
                return new_head;
            }
            tail = &mut node.next;
        }
        head
    }
}