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个node,从那开始到结尾和之前那部分对调,那个例子就是,4->5拿前面来,1->2->3拿后面去。
几个特殊:
k是可以大于整个list的长度的,所以这时要对k对len取模
如果取模之后得0,相当于不用rotate,直接返回
处理完特殊情况后,就用熟悉的faster/slower双指针解决就好(看到这种linkedlist,倒着数数的,就条件反射了)
先对faster设步长为n,然后faster和slower再一起走,知道faster.next==null,说明slower指向要倒着数的开始点的前一个位置。
所以slow.next就是要返回的newhead,保存一下。
然后把faster.next接到head上,slower.next存为null,作队尾。
这样就把list给rotate了。
这是我想的一种解法,还有一种就是把整个list连起来,变成环,找到切分点断开就行。
解法1:
1 public ListNode rotateRight(ListNode head, int n) {
2 if(head==null||head.next==null||n==0)
3 return head;
4 ListNode fast = head, slow = head,countlen = head;
5 ListNode newhead = new ListNode(-1);
6 int len = 0;
7
8 while(countlen!=null){
9 len++;
countlen = countlen.next;
}
n = n%len;
if(n==0)
return head;
for(int i = 0; i < n; i++)
fast = fast.next;
while(fast.next!=null){
slow = slow.next;
fast = fast.next;
}
newhead = slow.next;
fast.next = head;
slow.next = null;
return newhead;
}
解法2:
1 public ListNode rotateRight(ListNode head, int n) {
2
3 if (head == null || n == 0)
4 return head;
5 ListNode p = head;
6 int len = 1;//since p is already point to head
7 while (p.next != null) {
8 len++;
9 p = p.next;
}
p.next = head; //form a loop
n = n % len;
for (int i = 0; i < len - n; i++) {
p = p.next;
} //now p points to the prev of the new head
head = p.next;
p.next = null;
return head;
}
Reference for 2: http://leetcodenotes.wordpress.com/2013/08/14/leetcode-rotate-list-%E6%8A%8A%E5%90%8Ek%E4%B8%AArotate%E5%88%B0list%E5%89%8D%E9%9D%A2%E5%8E%BB%EF%BC%8Ck%E5%8F%AF%E4%BB%A5%E8%B6%85%E8%BF%87list%E6%9C%AC%E8%BA%AB%E9%95%BF%E5%BA%A6/
最新文章
- memcache和redis区别
- 理解CSS中的数学表达式calc()
- 云计算之路-阿里云上:Web服务器遭遇奇怪的“黑色30秒”问题
- python基础-range用法_python2.x和3.x的区别
- join()、implode()函数
- C# eval()函数浅谈
- MFC ListControl用法
- javaScript 删除数组中指定元素
- Css 应用一
- 开放源代码的微微信.NET 0.8 版公布了
- Nyoj Arbitrage(Floyd or spfa or Bellman-Ford)
- Luogu1486郁闷的出纳员【Splay】
- gulp一般使用
- Android进阶(十九)AndroidAPP开发问题汇总(三)
- P3414 SAC#1 - 组合数 题解
- EF框架引用问题
- 通过几个例子看sed的模式空间与保持空间
- geeksforgeeks-Array-Rotation and deletion
- 1 认识开源性能测试工具jmeter
- EHR ORA--1187由于验主频雘失败而无法从文件读取 ORA-01110数据文件temp01.dbf
热门文章
- 2018年全国多校算法寒假训练营练习比赛(第一场)J - 闯关的lulu
- spring boot上传文件错误The temporary upload location [/tmp/tomcat.5260880110861696164.8090/work/Tomcat/localhost/ROOT] is not valid
- iOS 11开发教程(十一)了解iOS11应用视图
- nova event
- 【差分约束系统/DFS版SPFA】BZOJ3436-小K的农场
- shell中set的用法(转)
- Node.js是一个事件驱动I/O服务端JavaScript环境
- oracle sql语句怎么查询所有存储过程中是否包含某个注释?
- ibatis实战之中的一个对多关联
- 使用静态库的一些问题 -all_load