目录
- 题目描述:
- 输入:
- 输出:
- 代码描述:
题目描述:
给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。
输入:
head = [1,2,3,4,5], k = 2
输出:
[4,5,1,2,3]
代码描述:
/**
* 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) {
if (head == null || head.next == null || k == 0) {
// 链表长度为1或者0,移动数为0的情况
return head;
}
int length = 0;// k大于链表长度时,length为链表长度,判断是否进行递归调用
ListNode low = head;// 指向移动之后的链表的尾结点
ListNode high = head;// 指向移动之前的链表的尾结点
// 确定high的第一次指向
for (int i = 0; i < k; i++) {
high = high.next;
length++;
if (high == null) {// 如果移动数 > 链表长度,则递归调用一次
return rotateRight(head, k % length);// 对k取模
}
}
while (high.next != null) {// 两个指针之间要保持相对位置
low = low.next;// 指向距离尾部结点的前(链表长度-k)个单位的结点
high = high.next;// 指向当前链表尾部
}
high.next = head;// 初始尾结点指向初始头结点,形成循环链表
head = low.next;// 头指针指向移动之后的头结点,也就是循环链表的尾结点的下一个结点
low.next = null;// 将移动之后的链表的尾结点指向null,即断开链表
return head;
}
}