61-旋转链表

1、首先得理解链表结构、理解环形链表

• 定义链表结构

leetcode: https://leetcode-cn.com/problems/rotate-list/

题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

旋转链表: 简单来说 ，是将尾部向前数第K个元素作为头，原来的头接到原来的尾上

思路

• 1、判断是否是链表、是否传入k 【空链表/只有一个节点的链表/移动步数为0 => 直接返回头结点】
• 2、首先计算出链表的长度 length，并找到该链表的末尾节点，将其与头节点相连。这样就得到了闭合为环的链表
  • 原来的尾节点 指向 头节点head，形成闭环链表，即原来的尾节点作为头了
• 3、得到环形链表之后，就计算获取移动k位置之后的 末节点位置
  • 获取末节点位置 实际上就是移动的步数move
• 4、根据移动的步数move来循环次数，寻找截断点 ，从而得到移动后的头指针
• 5、得到移动后的头指针，进行保存，然后把之前的环状链表就可以截断成普通链表，设最后的尾节点设为null即可将环状链表变成普通链表

js

// 定义链表结构
function ListNode(val, next) {
  this.val = val;
  this.next = next;
}
// 简单来创建链表的节点 【可实现append方法来添加节点】
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

// 旋转链表
var rotateRight = function (head, k) {
  //判断是否是链表、是否传入k 【空链表/只有一个节点的链表/移动步数为0 => 直接返回头结点】
  if (!head || !head.next || !k) return head; //特判
  let len = 1,
    cur = head;
  while (cur.next) {
    cur = cur.next; //最后一个节点
    len++; //拿到链表总长度
  }
  //最后一个节点的next指向头节点相连，形成环形链表
  cur.next = head; //连接成环形链表
  // 移动后的获取末尾节点位置
  let move = len - (k % len); //取模计算实际移动的步数
  while (move) {
    cur = cur.next; //根据move移动指针寻找截断点
    move--;
  }
  const result = cur.next; //保存截断点之后的点result（也就是新链表的头结点）
  cur.next = null; //截断成普通链表
  return result; //返回新链表的头结点
};

const result = rotateRight(node1, 2);
console.log(result);