61. 旋转链表

题意：

解题思路：

思路：时间复杂度是 O(n)
1. 计算链表长度，走到链表尾部；
2. 首尾相连；
3. 移动 k 个位置，找到结束点；
4. 断开结束点；
5. 返回结果值；

图示：

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function rotateRight($head, $k) {
        $p = $head;
        $length = 1;
        while ($p->next != null) {
            $p = $p->next;
            $length++;
        }
        //头尾相连
        $p->next = $head;
        //如果k大于length会造成跳多圈的情况，所以可以采用取模避免重复
        for ($i = 1; $i < $length - ($k % $length); $i++) {
            $head = $head->next;
        }
        $res = $head->next;
        $head->next = null;
        return $res;
    }
    function rotateRight1($head, $k) {
        $p = $head;
        $length = 1;
        while ($p->next != null) {
            $p = $p->next;
            $length++;
        }
        //尾部指向头部，形成环
        $p->next = $head;
        //如果k大于length会造成跳多圈的情况，所以可以采用取模避免重复
        $l = $length - ($k % $length);
        //跳几步，找到结束点
        $newEnd = $head;
        for ($i = 1; $i < $l; $i++) {
            $newEnd = $newEnd->next;
        }
        $newHead = $newEnd->next;
        //断开
        $newEnd->next = null;
        return $newHead;
    }
}

GO代码实现：

/**
 * 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
    }
    p := head
    length := 1
    for p.Next != nil {
        length++
        p = p.Next
    }
    p.Next = head
    p = head
    for i := 1; i < (length - k % length); i++ {
        p = p.Next
    }
    res := p.Next
    p.Next = nil
    return res
}