【061-Rotate List(旋转单链表)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题
Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
题目大意
向右旋转一个单链表,旋转k个位置,k非负数。
解题思路
用一个辅助root结点连接到链表头,先找到要移动的第一个结点的前驱prev,,再将prev后的所有结点接到root后面,再将组成一个旋转后的单链表。
代码实现
链表结点类
public class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}
算法实现类
public class Solution {public ListNode rotateRight(ListNode head, int n) {if (head == null || n < 1) {return head;}ListNode root = new ListNode(0);root.next = head;ListNode p = root;ListNode q = root;int count = 0;for (int i = 0; i <=n; i++) {p = p.next;count++;if (p == null) {count–; // 链表中除头结点后数据个数n = n % count; // 实际要位置的位数// 为重新开始位移做准备i = 0;p = head;}}(p != null) {p = p.next;q = q.next;}p = q;q = root;if (p != null && p.next != null) { // 有要位移的结点ListNode node;while (p.next != null) {// 摘除结点node = p.next;p.next = node.next;// 接上结点node.next = q.next;q.next = node;q = node; // 最后一个移动的节点}}return root.next;}}评测结果
点击图片,鼠标不释放,拖动一段位置,释放后在新的窗口中查看完整图片。
特别说明欢迎转载,转载请注明出处【】
别为荒漠的艰难而哭泣,只为奔流入海功成名就那一天,