[Leetcode][python][Java]Reverse Linked List/Reverse Linked List II/反转链表/反转链表 II
[Leetcode][python][Java]Reverse Linked List/Reverse Linked List II/反转链表/反转链表 II
蛮三刀酱
发布于 2019-03-26 16:01:10
发布于 2019-03-26 16:01:10
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
这里写图片描述
但是按照上述网页，如果写成：
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会得到：
[5,4,3,2,1,None]最后的dummy节点会是None保留在最后
应该写为把dummy都替换成dummy.next：
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
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问题
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
题目大意
翻转指定位置的链表
解题思路
将中间的执行翻转，再将前后接上
代码
迭代
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总结
链表难在理解，经典题目。这里整理的解法都是容易理解的，好好看吧。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年10月31日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录