首页 > 代码库 > Rotate List

Rotate List

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.

思路比较简单,就是先将链表首尾相连然后再从新切割,直接贴代码吧

 1 public ListNode rotateRight(ListNode head, int n) {
 2         // 计数,并构造环状链表
 3         if (head == null || head.next == null || n == 0) {
 4             return head;
 5         }
 6         int count = 1;
 7         ListNode p = head;
 8         while (p.next != null) {
 9             p = p.next;
10             count++;
11         }
12         p.next = head;
13         n = (n - 1) % count + 1;
14         n = (2 * count - n - 1) % count;
15         p = head;
16         for (int i = 0; i < n; i++) {
17             p = p.next;
18         }
19         head = p.next;
20         p.next = null;
21         return head;
22     }

 

这题还是比较好想,但是遇到点问题,就是负数取模,负数取模是实现相关的,标准没有规定。在java中-1%5=-1,这一点让我调试了半天才发现,需要注意

顺便把Unique Paths那个题遇到的问题也贴出来吧,题目思路很简单,是组合问题,求n+m-2中取n-1个有多少种取法,注意计算的时候求乘法可能会超出int所表示的范围!!!!

 1 public int uniquePaths(int m, int n) {
 2         long count = 1;
 3         if (m == 1 || n == 1) {
 4             return 1;
 5         }
 6         m--;
 7         n--;
 8         for (int i = m + 1; i <= n + m; i++) {
 9             count *= i;
10             count /= (i - m);
11         }
12         return (int) count;
13     }