A******g
发帖数: 612 | 1 Leetcode上这题 reverse linked list II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Google了一个解法，https://gist.github.com/eclipse9614/4757816
通过测试了
根据这个算法，模拟一下
如图，好像不是很对，肯定是我理解有问题
搞了一晚上了，太挫了！ |
p*g
发帖数: 141 | 2 pass OJ
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode preHead = new ListNode(1), cur=head;
preHead.next = head;
for ( int i=0; i
cur = cur.next;
preHead = preHead.next;
}
ListNode tail = cur;
for ( int i=m; i<=n; i++) {
ListNode t = cur.next;
cur.next = preHead.next;
preHead.next = cur;
cur = t;
}
tail.next = cur;
return m==1? preHead.next:head;
}
【在 A******g 的大作中提到】
: Leetcode上这题 reverse linked list II
: Reverse a linked list from position m to n. Do it in-place and in one-pass.
: For example:
: Given 1->2->3->4->5->NULL, m = 2 and n = 4,
: return 1->4->3->2->5->NULL.
: Google了一个解法，https://gist.github.com/eclipse9614/4757816
: 通过测试了
: 根据这个算法，模拟一下
: 如图，好像不是很对，肯定是我理解有问题
: 搞了一晚上了，太挫了！
|
A******g
发帖数: 612 | |
p*****p
发帖数: 379 | 4 这人写的略乱……
按他的意思
mHead是m点那个
nNode是n后面那个
tmphead造出来不知道干嘛用的
这题用递归容易看
【在 A******g 的大作中提到】
: Leetcode上这题 reverse linked list II
: Reverse a linked list from position m to n. Do it in-place and in one-pass.
: For example:
: Given 1->2->3->4->5->NULL, m = 2 and n = 4,
: return 1->4->3->2->5->NULL.
: Google了一个解法，https://gist.github.com/eclipse9614/4757816
: 通过测试了
: 根据这个算法，模拟一下
: 如图，好像不是很对，肯定是我理解有问题
: 搞了一晚上了，太挫了！
|
c********t
发帖数: 5706 | 5 赞图
这道题很难写对，
先试试把 reverse whole list 写对。
然后m to n 就是如何把头尾与原来的连接好了
还有就是多用变量。
【在 A******g 的大作中提到】
: Leetcode上这题 reverse linked list II
: Reverse a linked list from position m to n. Do it in-place and in one-pass.
: For example:
: Given 1->2->3->4->5->NULL, m = 2 and n = 4,
: return 1->4->3->2->5->NULL.
: Google了一个解法，https://gist.github.com/eclipse9614/4757816
: 通过测试了
: 根据这个算法，模拟一下
: 如图，好像不是很对，肯定是我理解有问题
: 搞了一晚上了，太挫了！
|
A******g
发帖数: 612 | 6 谢谢大家指点！ 用recursion果然很快写完了，而且比较容易看懂 |
r*********n
发帖数: 4553 | 7 i know this is cheating, but can't you just swap the values of the two nodes
? |
l*******b
发帖数: 2586 | 8 反转整个链表貌似好写点, 反转 m, n需要有几个边角情况, leetcode上的解法挺好呀.
val c = List(1,2,3,4,5)
def rev(x:List[Int], t:List[Int]) : List[Int] = {
if (x.tail == Nil) return x ::: t
else rev(x.tail, x.head :: t)
}
rev(c, Nil)
得到
res1: List[Int] = List(5, 4, 3, 2, 1) |
i********m
发帖数: 332 | 9 练习了
public ListNode reverseBetween(ListNode head, int m, int n) {
// Start typing your Java solution below
// DO NOT write main() function
int diff = n-m;
if (diff < 0 || m <= 0)
return null;
boolean flag = false;
ListNode cur = head;
ListNode prev = head;
while (m-- > 1) {
if (cur == head) {
cur = cur.next;
}
else {
cur = cur.next;
prev = prev.next;
}
if (cur == null) {
return null;
}
}
ListNode newHead = cur;
ListNode newPrev = newHead;
if (newHead == head)
flag = true;
while (diff-- > 0 ){
if (cur == null)
return null;
if (cur == newHead) {
cur = cur.next;
if (cur == null)
return null;
}
newPrev.next = cur.next;
cur.next = newHead;
newHead = cur;
cur = newPrev.next;
}
if (flag == false){
prev.next = newHead;
return head;
}
else
return newHead;
} |
A*****i
发帖数: 3587 | 10 这做法我觉得很好
很多情况下list里面的data都存的不过是个索引而已，C/C++下面存对象(数据)的地址
，java下存的是reference，就算真存的是int或者单一的数据也很简单，根本没有必要
来操作那个next指针
但是面试官能不能过就另一回事
nodes
【在 r*********n 的大作中提到】
: i know this is cheating, but can't you just swap the values of the two nodes
: ?
|
A******g
发帖数: 612 | 11 链表没有random access，swap value的话要jump back and forth， 复杂度大概是O(N
^2)。 recursion的话等于把每个节点的地址都存到stack里，所以时间是O(N),空间也
是O(N)。 话说回来，如果先用一个array把每个链表节点的地址存起来，那么既可以反
转next，也可以swap value, 都是O(N)，和recursion一样了，code也挺好写。
谢谢你给的灵感！ 对这题的认识又加深了。
nodes
【在 r*********n 的大作中提到】
: i know this is cheating, but can't you just swap the values of the two nodes
: ?
|
c********t
发帖数: 5706 | 12 Think again
(N
★ 发自iPhone App: ChineseWeb 7.8
【在 A******g 的大作中提到】
: 链表没有random access，swap value的话要jump back and forth， 复杂度大概是O(N
: ^2)。 recursion的话等于把每个节点的地址都存到stack里，所以时间是O(N),空间也
: 是O(N)。 话说回来，如果先用一个array把每个链表节点的地址存起来，那么既可以反
: 转next，也可以swap value, 都是O(N)，和recursion一样了，code也挺好写。
: 谢谢你给的灵感！ 对这题的认识又加深了。
:
: nodes
|
