Reverse Linked List
题目大意
翻转链表
解题思路
必看：
http://blog.csdn.net/autumn20080101/article/details/7607148
以下代码若理解不通请务必务必务必务必务必务必务必看上方网页
还可以参考（迭代+递归）：
https://blog.csdn.net/u011608357/article/details/36933337
代码
迭代
循环迭代体是：
next = head->next;
head->next = prev;
prev = head;
head = next;
循环终止条件是：
head == NULL
但是按照上述网页，如果写成：
1
2
3
4
5
6
7
8
9
10
11
12
13
| lass Solution(object): # 迭代
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(None)
while head: # 终止条件是head=Null
nextnode = head.next # nextnode是head后面的节点
head.next = dummy # dummy.next是Null，所以这样head.next就成为了Null
dummy = head # head当前数组给dummy.next
head = nextnode # head向后一位
return dummy
|
会得到：
最后的dummy节点会是None保留在最后
应该写为把dummy都替换成dummy.next：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution(object): # 迭代
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(None)
while head: # 终止条件是head=Null
nextnode = head.next # nextnode是head后面的节点（保持下个节点信息不丢）
head.next = dummy.next # dummy.next是Null，所以这样head.next就成为了Null
dummy.next = head # head当前数字给dummy.next
head = nextnode # head向后一位
return dummy.next
|
或者用prev代替dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution(object): # 迭代
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(None)
prev = dummy.next
while head: # 终止条件是head=Null
nextnode = head.next # nextnode是head后面的节点
head.next = prev # dummy.next是Null，所以这样head.next就成为了Null
prev = head # head当前数组给dummy.next
head = nextnode # head向后一位
return prev
|
这样就成功通过。
以后不理解先记上面的，然后再改为下面的。
递归
上面网页进行了解析，没怎么理解，有空下次继续。。。
Java
直接上面第一个代码的思路就可以，不会有最后有null问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null)
return null;
//head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
ListNode pre = null;
ListNode nextnode = null;
while(head!=null){
nextnode = head.next;
head.next = pre;
pre = head;
head = nextnode;
}
return pre;
}
}
|
Reverse Linked List II
题目大意
翻转指定位置的链表
解题思路
将中间的执行翻转，再将前后接上
代码
迭代
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution(object): # 迭代
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
# 例如[1,2,3,4,5]
dummy = ListNode(-1)
dummy.next = head
node = dummy
for __ in range(m - 1): # 1
node = node.next
prev = node.next # prev.val = 2
curr = prev.next # curr.val = 3
for __ in range(n - m): # 翻转2次，和直接翻转全部链表不同的是，这里条件就是翻转次数，不通过head指向null判断，毕竟也不指向null，后面还有数字
nextnode = curr.next
curr.next = prev
prev = curr
curr = nextnode
node.next.next = curr # curr是翻转链表后面的链表
node.next = prev # prev是翻转链表前面的链表
return dummy.next
|
总结
链表难在理解，经典题目。这里整理的解法都是容易理解的，好好看吧。