0061.rotate-list.md

0061.Rotate-List

Description

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

Example 2:

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

Tags: Linked List

题意

给定一个链表和一个数字，将单链表向右移动 k 位。

题解

思路1

1. 先计算出链表的长度，判断 k 是否大于链表的长度。
2. 如果 k 大于链表的长度，取 k = k % len(LinkedList)
3. 将链表变为环形链表。
4. 移动 length - k - 1 位，然后断开链表。

/*
 * @lc app=leetcode id=61 lang=golang
 *
 * [61] Rotate List
 */
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if nil == head || 0 == k {
        return head
    }
    head, length := cycleList(head)
    if k >= length {
        k = k % length
    }
    for i := 0; i < length - k - 1; i++ {
        head = head.Next
    }
    p := head.Next
    head.Next = nil
    return p
}

func cycleList(l *ListNode) (*ListNode, int) {
    head, length := l, 1
    for l.Next != nil {
        l = l.Next
        length++
    }
    l.Next = head
    return head, length
}

结语

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-golang-algorithm