Leetcode - Rotate List

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

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

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

If this is an array problem, it can be solved by reversing the whole array and then reversing each part. But this is a linked list problem, so it can be solved by just iterating the linked list and finding the newHead and newTail. Set newTail.Next to nil and tail.Next = head. And then return newHead

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil || k == 0 {
        return head
    }
    size := 1
    node := head
    for node.Next != nil {
        node = node.Next
        size++
    }
    //fmt.Println("size: ", size)
    if k >= size {
        k = k%size
    }
    if k == 0 {
        return head
    }
    tail := node
    j := size - k
    
    node = head
    for j > 1 {
        node = node.Next
        j--
    }
    //fmt.Println("node: ", node)
    newTail := node
    newHead := node.Next
    newTail.Next = nil
    tail.Next = head    
    
    return newHead
}

• 相关文章
• 全局相关文章