【Leetcode链表】反转链表 II（92）

题目

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

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

解答

一轮指针变换，时间复杂度O(n)，空间复杂度O(1)

首先，在链表头部新建两个空节点thead、p2，令p、p3指向thead，c指向head，所有指针往后移动m个位置，p3始终和p相差n-m个位置（记录反转链表的第一个节点），开始向后反转n-m个节点。

反转完成后，p处于反转链表的最后一个位置，p3反转链表的第一个位置，p2处于反转链表的前一个节点，c处于反转链表的额后一个节点。因此，令p2指向p，p3指向c即可，另外需要注意，若链表从头开始反转，则return p指针即可。

# Definition for singly-linked list.

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:

        if not head.next or m==n:

            return head

        n2, m2 = n, m

        thead = ListNode(-1)

        thead.next = head

        p, p3 = thead, thead

        p2 = ListNode(-1)

        p2.next = thead

        c = head

        # 指针就位

        while m:

            p2 = p2.next

            p = p.next

            p3 = p3.next

            c = c.next

            m -= 1

        # 反转

        Q = n2-m2

        while Q:

            n = c.next

            c.next = p

            p = c

            c = n

            Q -= 1

        p2.next = p

        p3.next = c

        #　从头反转

        if m2==1 and n2!=m2:

            return p

        return thead.next

巴特西

【Leetcode链表】反转链表 II（92）

题目

解答

最新文章

热门文章