旋转链表

[louzhedong]

习题

出处：LeetCode 算法第61题

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

示例 1:

输入: 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

示例 2:

输入: 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

思路

首先我们可以遍历k次，每次都使链表右移一个位置，但这样会超时。

经过观察可以发现，没经过一轮链表长度的移动，链表会变成初始状态。我们设链表长度为count，所以我们只要移动k % count 次链表即可

解答

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  if (head == null || head.next == null) {
      return head;
  } 
  var count = 0;
  var ptr = head;
  while(ptr != null) {
      ptr =ptr.next;
      count++;
  }
  var loop = k % count;
  for (var i = 0; i< loop;i++) {
      var prev = head;
      var start = prev.next;
      while (start.next != null) {
          prev = prev.next;
          start = start.next;
          
      } 
      start.next = head;
      prev.next = null;
      head = start;
  }
  return head;
};