Rotate List
今天是一道有关链表的题目，来自LeetCode，难度为Medium，Acceptance为22%。
题目如下
Given a list, rotate the list to the right by k places, where k is non-negative.
Example
Given1->2->3->4->5andk = 2,
return4->5->1->2->3.
解题思路及代码见阅读原文
回复0000查看更多题目
解题思路
该题的思路较为简单。
首先，回忆一下删除倒数第k个节点的题目。用两个指针，一个先走k步，然后一快一慢，直到快指针为null，慢指针指向的节点即为我们要删除的节点。更多细节会在后续的题目中推送。
然后，该题的思路与之类似。即找到倒数第k个节点，让其next指向null。链表的最后一个节点指向表头。
需要注意的是k一定是小于链表长度的，因此首先应该将k对链表的长度取模。
下面是代码
代码如下
java版
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param head: the List
* @param k: rotate to the right k places
* @return: the list after rotation
*/
public ListNode rotateRight(ListNode head, int k) {
// write your code here
if(head == null || k <= 0)
return head;
k = k % getLength(head);
if(k == 0)
return head;
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < k; i++) {
fast = fast.next;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
ListNode result = slow.next;
slow.next = null;
fast.next = head;
return result;
}
private int getLength(ListNode head) {
int length = 0;
while(head != null) {
head = head.next;
length++;
}
return length;
}
}
关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助
image
