170. Rotate List

Leave a comment

September 4, 2016 by oneOokay

用快慢指针做。
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 || head.next == null) {
return head;
}

ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = head; //will be the end of the new list
int i = 0;

—-这一段可以用 k = k % linkedList.length 来代替–
while (i < k) { //决定快慢指针的位置
if (fast.next != null) {
fast = fast.next;
}else {
fast = head; //当 k大于linkedlist的长度时,回到head重新开始。
}
i ++;
}

——–
while (fast.next != null) { //移动快慢指针
fast = fast.next;
slow = slow.next;
}
//重新连接相关节点
fast.next = dummy.next;
dummy.next = slow.next;
slow.next = null;
return dummy.next;
}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: