Paste_Image.png
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k < 0)
return head;
else if (head.next == null)
return head;
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode tail = head;
int total = 1;
while (tail.next != null) {
tail = tail.next;
total++;
}
k = k % total;
if (k == 0)
return dummy.next;
ListNode curr = dummy;
for (int i = 0; i < (total - k); i++)
curr = curr.next;
if (curr.next == null)
return dummy.next;
ListNode newHead = curr.next;
curr.next = null;
tail.next = dummy.next;
dummy.next = newHead;
return dummy.next;
}
public static void main(String[] args) {
Solution test = new Solution();
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
System.out.println(test.rotateRight(n1, 3));
}
}
My test result:
Paste_Image.png
這次題目也不難波闹。先遍歷一遍找出總個數(shù) total
然后根據(jù) total - k 找到那個斷裂點一喘。斷開驱还。在用dummy和新的頭接上。
原來的頭接到tail后面去凸克，就差不多了议蟆。
主要我是沒能理解， k >= total 是什么意義萎战。
查了之后發(fā)現(xiàn)咐容，做一個 k = k % total 處理就行了。
**
總結(jié)： LinkedList rotate
**
Anyway, Good luck, Richardo!
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null)
return null;
int n = 1;
ListNode temp = head;
ListNode tail = head;
while (temp.next != null) {
n++;
temp = temp.next;
tail = temp;
}
k = k % n;
if (k == 0)
return head;
temp = head;
for (int i = 1; i < n - k; i++) {
temp = temp.next;
}
ListNode newHead = temp.next;
temp.next = null;
tail.next = head;
return newHead;
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(4);
ListNode n5 = new ListNode(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
Solution test = new Solution();
ListNode head = test.rotateRight(n1, 2);
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + "->");
temp = temp.next;
}
}
}
有一個 corner case沒有考慮到蚂维，當k= 0 時戳粒，這個時候是不需要旋轉(zhuǎn)的，如果強制旋轉(zhuǎn)虫啥， newHead = tail.next -> null. 會出錯蔚约。
Anyway, Good luck, Richardo!
My code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k < 0 || head == null) {
return null;
}
ListNode tail = head;
int total = 0;
while (tail.next != null) {
total++;
tail = tail.next;
}
total++;
k = k % total;
if (k == 0) {
return head;
}
int counter = total - k - 1;
ListNode curr = head;
while (counter > 0) {
curr = curr.next;
counter--;
}
ListNode newHead = curr.next;
curr.next = null;
tail.next = head;
return newHead;
}
}
k = 0 的時候，不需要rotate涂籽，直接返回就行苹祟。
Anyway, Good luck, Richardo! -- 08/16/2016
