【链表】 61. 旋转链表

61. 旋转链表

解题思路

• 首先计算出链表长度
• 将链表长度进行取余
• 遍历链表 对链表进行分割 得到两个子链表
• 重新连接两个链表
• 比如1 2 3 4 5 k= 2 进行分割得到 1 2 3 和 4 5两个子链表

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {// 首先计算出链表长度// 将链表长度进行取余 // 遍历链表 对链表进行分割  得到两个子链表// 重新连接两个链表// 比如1 2 3 4 5  k= 2 进行分割得到 1 2 3 和 4 5两个子链表if(head == null){return null;}ListNode dummyNode = new ListNode(0);// 定义一个哑结点dummyNode.next = head;ListNode p = head;int count = 0;while(p != null){p = p.next;count++;}int x =  k % count;// 真实需要移动的节点个数// 找到倒数第x + 1个节点int y = count - x;p = dummyNode;for(int i = 0; i < y; i++){p = p.next;// 移动节点}ListNode q = p.next;// 说明一个节点都不需要移动if(q == null){return dummyNode.next;}p.next = null;// 将该节点的下一个节点置为null// 开始连接链表dummyNode.next = q;while(q.next != null){q = q.next;// 找到最后一个节点}q.next = head;return dummyNode.next;}
}