链表之旋转链表

原题

这是一道考察单向链表操作的题目：leetcode61

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

例如：

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

又如：

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

题目简单易懂，但是要注意的是：
要保持表整体数据不变，主要改变的是节点间的位置关系，且转换以后尾节点的 next 指针需重新指向 NULL。

单向链表描述

单向链表最基本的元素是节点，它主要由两部分组成：

1. 值（数据）
2. 下个节点指针（引用）

构造函数如下：

function ListNode (val, next) {
  this.val = val || 0;
  this.next = next || null;
}

构建单向链表

对一个数组新建单向链表：

function createLinkedlist (array) {
	var sentinel = new ListNode(),
		len = array.length,
		p, i;

	p = sentinel;
	// 遍历数据并新建节点
	for (i = 0; i < len; i++) {
		p.next = new ListNode(array[i]);
		p = p.next;
	}
	// 返回真正的头节点
	return sentinel.next;
}

好~正式进入解题部分。

题解

先说思路，主要有三点：

1. 如果此链表长度为 n，考虑到 k 有可能大于 n，则实际右移的次数可简化为 k % n。比如第一个例子中，k 为 6 的情况与 k 为 1 的情况一样。
2. 可以先忽略末尾的 NULL，直接将尾节点 next 指向头节点形成回环方便操作。
3. 按照链表方向，同时移动头指针与尾指针 n - k % n 次。

实现代码：

function rotateRight (head, k) {
  if (!head || !head.next) return head
  // 求出尾节点与长度
  let tail = head
  let len = 1
  while (tail.next) {
    tail = tail.next
    len++
  }
  // 计算真实 k
  let realK = k % len
  // 形成回环
  tail.next = head

  for (let i = 0; i < len - realK; i++) {
    head = head.next
    tail = tail.next
  }
  // tail 重新指向 null
  tail.next = null
  return head
}

其中，时间复杂度为 O(n)，空间复杂度为O(1)。