[Leetcode][python][Java]Reverse Linked List/Reverse Linked List II/反转链表/反转链表 II

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

总结

链表难在理解,经典题目。这里整理的解法都是容易理解的,好好看吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小L的魔法馆

POJ 1410--Intersection(判断线段和矩形相交)

Intersection Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

19930
来自专栏小L的魔法馆

HDU 6354--Everything Has Changed(判断两圆关系+弧长计算)

11150
来自专栏小L的魔法馆

2018 Wannafly summer camp Day3--Knight

Knight 题目描述: 有一张无限大的棋盘,你要将马从(0,0)(0,0)(0,0)移到(n,m)(n,m)(n,m)。 每一步中,如果马在(x,...

7930
来自专栏逍遥剑客的游戏开发

C#脚本实践(四): 反射与序列化

15050
来自专栏小L的魔法馆

HDU 6330--Visual Cube(构造,计算)

9150
来自专栏小L的魔法馆

atan和atan2反正切计算

返回值 若不出现错误,则返回 arg 在[−π/2;+π/2][−π/2;+π/2] [- π/2 ; +π/2] 弧度范围中的弧(反)正切( arctan...

27060
来自专栏Python程序员杂谈

从问题到探索--从slice说起

如果你是新手,你发现你对于别人说的一切都表示有疑问,那么恭喜你!你拥有大部分编程老手已经遗忘的能力——对细节的敏感。善于发现问题是一个很好的习惯,接触的东西多了...

8420
来自专栏小L的魔法馆

POJ 1113--Wall(计算凸包)

Wall Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40363 ...

10330
来自专栏小L的魔法馆

2018 Wannafly summer camp Day3--Travel

Travel 描述 题目描述: 魔方国有n座城市,编号为1∼n1∼n1\sim n。城市之间通过n-1条无向道路连接,形成一个树形结构。

12430
来自专栏Python程序员杂谈

由__future__中unicode_literals引起的错误来研究python中的编码问题

在py2.7的项目中用了future模块中的 unicode_literals 来为兼容py3.x做准备,今天遇到一个UnicodeEncodeError的错误...

12810

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励