- 旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
示例 2：
输入：head = [0,1,2], k = 4
输出：[2,0,1]
题解：
/** * 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)return head; int len =1; ListNode oldTail = head; while (oldTail.next!=null) { oldTail = oldTail.next; len++; } oldTail.next = head; ListNode newTail = head; for(int i =0; i < len - k% len -1; i++){ newTail = newTail.next; } ListNode newHead = newTail.next; newTail.next =null; return newHead; } }
详尽解析版：
class Solution { public ListNode rotateRight(ListNode head, int k) { // 1. 特判 if(k == 0 || head == null || head.next == null){ return head; } // 2. 计算出原链表的长度为n int n = 1; ListNode iter = head; while(iter.next != null){ iter = iter.next; n++; // 此时n记录的是链表的末尾节点 } // 3. 找到移动k位后新链表的最后一个节点 int add = n - k % n; // add 记录的是新链表的最后一个节点 if(add == n){ // 如果k 刚好为n的整数倍数，新链表将于原链表相同 return head; // 直接返回原链表即可 } // 4. 处理逻辑 iter.next = head; // 将当前链表闭合为环 while(add-- > 0){ // 将iter指向新链表的最后一个节点位置 iter = iter.next; } ListNode ret = iter.next; // 此时 ret为移动k位后新链表的头 iter.next = null; // 将环断开 return ret; // 返回新链表 } }
