leetcode-92 | 反转链表II

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解答思路

类似的使用取数据，组成数据正确集，生成格式

翻译如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        li = []
        p = head
        m, n = m-1, n-1
        while p:
            li.append(p.val)
            p = p.next

        i,j = m, n
        while i <= j:
            li[i], li[j] = li[j], li[i]
            i+=1
            j-=1

        head = ListNode(li[0])
        p = head
        for i in range(1,len(li)):
            s = ListNode(li[i])
            p.next = s
            p = p.next
        p.next = None

        return head

结果：

执行用时 : 40 ms, 在Reverse Linked List II的Python提交中击败了27.61% 的用户
内存消耗 : 11.8 MB, 在Reverse Linked List II的Python提交中击败了36.22% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	40 ms	11.8MB	python

很老土的解法

遍历获取数据，翻转，构成数据格式

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None or head.next==None:
            return head
        #可以把数据全部整下来，在反转，在构成
        li = []
        p = head
        while p:
            li.append(p.val)
            p=p.next
        li.reverse()
        head = ListNode(li[0])
        p = head
        for i in range(1,len(li)):
            s = ListNode(li[i])
            p.next = s
            p=p.next

        p.next = None

        return head

结果：

执行用时 : 44 ms, 在Reverse Linked List的Python提交中击败了36.40% 的用户
内存消耗 : 15.7 MB, 在Reverse Linked List的Python提交中击败了16.62% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	44 ms	15.7MB	python

我们使用指针（推荐）

图解：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None or head.next==None:
            return head
        pre = None
        cur = head

        while cur:
            #由于如果cur为None的时候，是没有next的，所以我们将它放置到了循环中，判断非None生效，故而在这里声明我们的饿next指针
            next = cur.next

            #我们的移动逻辑
            cur.next = pre
            pre = cur
            cur = next

        return pre  #cur一定是None

结果：

执行用时 : 36 ms, 在Reverse Linked List的Python提交中击败了100.00% 的用户
内存消耗 : 13.3 MB, 在Reverse Linked List的Python提交中击败了50.21% 的用户

提交时间	状态	执行用时	内存消耗	语言
几秒前	通过	36 ms	13.3MB	python

分析： 如果用两个指针，如下图，是不好操作的。