旋转链表-中等

难度：中等

题目描述：
给定一个链表，旋转链表，将链表每个节点向右移动 *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

1
2
3
4
5
6

解题思路：
暴力解法，先转成数组旋转后再转换为链表

var rotateRight = function (head, k) {
  let arr = [];
  let current = head;
  while (current) {
    arr.push(current.val);
    current = current.next;
  }
  if (arr.length === 0) return head;
  if (k > arr.length) {
    k = k % arr.length;
  }
  if (k === 0) return head;
  arr.unshift(...arr.splice(arr.length - k, k));
  current = new ListNode(arr[0]);
  let i = 1;
  while (i < arr.length) {
    function add(head, num) {
      let c = head;
      while (c.next) {
        c = c.next;
      }
      c.next = new ListNode(num);
    }
    add(current, arr[i]);
    i++;
  }
  return current;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

第一次循环:
- 记录链表长度n
- 让链表闭合形成环形链表
第二次循环:
- 循环(k % n)次
- 然后在该指针处打断环形链表, 此时 return 头部节点就是答案

const rotateRight = (head, k) => {
  if (!head) return null;
  let curr = head,
    tmp = null,
    n = 0;
  while (curr) {
    n++;
    if (!curr.next) {
      curr.next = head;
      break;
    }
    curr = curr.next;
  }
  k = k % n;
  while (k++ < n) {
    k === n && (tmp = head);
    head = head.next;
  }
  tmp.next = null;
  return head;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第一步: 遍历一遍链表得到初始尾结点 last;
第二步: l 与 r 距离保持为 modK + 1;
第三步: l 与 r 同时向右移动, 直到 r 为 null, 则 l 为要分割的元素;

var rotateRight = function (head, k) {
  const dummy = new ListNode(0);
  dummy.next = head;
  let count = 0;
  let last = dummy;
  while (last.next) {
    last = last.next;
    count++;
  }

  if (count === 0 || count === k) return dummy.next;
  const modK = k % count;
  let diff = modK + 1;

  let l = dummy;
  let r = dummy;
  while (diff--) {
    r = r.next;
  }

  while (r) {
    r = r.next;
    l = l.next;
  }

  last.next = dummy.next;
  dummy.next = l.next;
  l.next = null;

  return dummy.next;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

← 链表的中间结点-简单相交链表-简单 →

# 旋转链表-中等

旋转链表-中等