Golang O(n) + O(1) space, accepted with explaination


  • 0
    V
    1. need to get a length of list
    2. if k == length - nothing to do, if k > length -> k = k mod length because we don't need to rotate the list over and over, we will know exactly how many characters should be moved to the head.
    3. find k elements from the end. Right part - head, left part - tail. Let's concatenate it.
    func RotateRight(head *ListNode, k int) *ListNode {
    	if k == 0 || head == nil || head.Next == nil { // check the input
    		return head
    	}
    
    	var current, prev, tmpHead, last *ListNode
    
    	current = head
    	count := 1
    
    	for current.Next != nil {
    		count++
    		current = current.Next
    	}
    	last = current
    
    	switch {
    	case k == count:
    		return head
    	case k > count:
    		k = k % count
    		if k == 0 {
    			return head
    		}
    	}
    
    	current = head
    
    	for current != nil {
    		count--
    		prev = current
    		current = current.Next
    
    		if count == k {
    			tmpHead = current
    			break
    		}
    	}
    
    	prev.Next = nil
    	last.Next = head
    
    	return tmpHead
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.