首页 > 试题广场 >

链表内指定区间反转

[编程题]链表内指定区间反转

热度指数：352345 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。
例如：
给出的链表为 $1\to 2 \to 3 \to 4 \to 5 \to NULL$ , $m=2,n=4$ ,
返回 $1\to 4\to 3\to 2\to 5\to NULL$ .

数据范围：链表长度 $0 < size \le 1000$ ， $0 < m \le n \le size$ ，链表中每个节点的值满足 $|val| \le 1000$

要求：时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

进阶：时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

示例1

输入

{1,2,3,4,5},2,4

输出

{1,4,3,2,5}

示例2

输入

{5},1,1

输出

{5}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Python3

想奋斗的三文鱼在攒经验

写代码的过程有些不太懂，为什么（给倒置的节点指向的下一个节点赋值为当前节点cur）和（给倒置的节点指向的下一个节点赋值为前驱节点的下一个节点）两个结果不一样

例如中间p.next=pre.next若改为p.next=cur结果就不一样了

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        newnode=ListNode(0)
        pre = newnode
        pre.next=head
        for i in range(1,m):
            pre=pre.next
        cur=pre.next
        for i in range(m,n):
            p=cur.next
            cur.next=p.next
            p.next=pre.next
            pre.next=p
        return newnode.next

发表于 2024-01-21 13:02:01 回复(2)

Python3

牛客869544143号

#有点类似双指针的做法

class Solution:

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

head_new = head

node_list = []

if head:

head_tmp = head

node_list.append(head_tmp)

while head_tmp.next:

head_tmp = head_tmp.next

node_list.append(head_tmp)

p = m-1

q = n-1

while(p<q):

node_list[p],node_list[q] = node_list[q],node_list[p]

p += 1

q -= 1

for i in range(len(node_list)-1):

node_list[i].next = node_list[i+1]

node_list[-1].next = None

else:

node_list.append(None)

return node_list[0]

编辑于 2024-01-16 22:18:50 回复(0)

Python3

牛客922061611号

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        if head == None:
            return head
        if n <= m:
            return head
        new_p = None
        record_head = None
        record_tail = None
        count = 1
        while head:
            if count < m:
                record_head = head
                head = head.next 
            elif count > n:
                record_tail = head
                head = head.next
            # else count >= m and count <= n:
            else:
                tmp = head.next
                head.next = new_p
                new_p = head
                head = tmp
            count += 1
        record_head.next = new_p
        q = record_head
        count = 0
        while count < n-1:
            record_head = record_head.next
            count += 1
        record_head.next = record_tail
        return q

发表于 2024-01-14 17:40:54 回复(0)

Python3

whime1024

缝缝补补，写的一塌糊涂，边界处理好难

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @param m int整型 
# @param n int整型 
# @return ListNode类
#
class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        count = n-m
        cur = head
        pre = ListNode(0)
        pre.next = head
        M=m
        while m>1:
            pre=cur
            cur = cur.next
            m -=1
        tmp1 = cur.next
        tail = cur
        tmp2 = tmp1.next if tmp1 else None
        while tmp1 and count:
            tmp2= tmp1.next
            tmp1.next = cur
            cur = tmp1
            tmp1 = tmp2
            count -=1
        pre.next = cur
        tail.next = tmp1

        return head if M>1 else pre.next

发表于 2023-10-17 15:40:19 回复(0)

Python3

Winnyting

类：

定义区间反转链表函数：

初始化虚拟链表res

定义res下一个节点为头节点

将res虚拟链表赋值给pre

实链表头节点赋值给cur

遍历第一个节点到区间上边界：

实链表赋值给pre

cur指向下一个节点

遍历反转区间：

cur的下一节点值赋值给临时变量temp

temp的下一个节点赋值给cur的下一个节点

temp赋值给pre下一个节点

返回虚拟链表res下一节点

发表于 2023-06-04 22:08:43 回复(0)

Python3

JKJ_

class Solution:

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

vals = []

cur = head

while cur:

vals.append(cur.val)

cur = cur.next

reverse = vals[m-1:n][::-1]

nvals = vals[:m-1]+reverse+vals[n:]

res = ListNode(-1)

cur = res

for i in nvals:

cur.next = ListNode(i)

cur = cur.next

return res.next

发表于 2023-03-21 15:35:25 回复(2)

Python3

我想吃饭呜呜呜

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        temp = head
        res = []
        length = 0
        while temp is not None:
            length += 1
            res.append(temp.val)
            temp = temp.next
        res1 = []
        if n<length:
            res1 = res[:m-1]+res[m-1:n][::-1]+res[n:]
        else:
            res1 = res[:m-1]+res[m-1:n][::-1]
        temp = head
        i = 0
        while temp is not None:
            temp.val = res1[i]
            temp = temp.next
            i += 1
        return head

发表于 2023-03-11 13:37:28 回复(0)

Python3

ling201909271034152

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        newHead = ListNode(0) # 附加一个头结点，使得空链表和非空链表得到统一
        newHead.next = head
        p = newHead # 反转部分的前一个指针，可以看做是反转部分的头结点
        cur = p.next
        i = 1
        while i < n:
            if i < m:
                p = cur
                cur = p.next
            else:
                # 永远想着把当前结点的后继变成反转部分的前驱，当前结点永远是反转部分的最后一个结点
                pre = cur.next
                cur.next = pre.next
                pre.next = p.next
                p.next = pre
            i += 1
        return newHead.next

发表于 2023-02-03 16:28:31 回复(0)

Python3

V1KIN

多练习，熟能生巧

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        # write code here
        p = ListNode(0)
        p.next = head  # 保证p.next存在
        new_head = p
        cur = None
        i = 1
        while i < n:
            if i < m:
                p = head
                head = head.next
            elif i >= m:
                cur = head.next
                head.next = cur.next  # 保证第n个节点之后的节点不丢失
                cur.next = p.next
                p.next = cur
            i += 1
        return new_head.next

发表于 2022-11-27 15:00:14 回复(1)

Python3

ヾ那一刻执着

successor = None

class Solution:

def trace(self, head, n):

global successor

if n == 1:

successor = head.next

return head

last = self.trace(head.next, n - 1)

head.next.next = head

head.next = successor

return last

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

# write code here

if m == 1:

return self.trace(head, n)

head.next = self.reverseBetween(head.next, m - 1, n - 1)

return head

发表于 2022-11-20 18:39:34 回复(0)

Python3

newMar

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        if m == n:
            return head

        lis = [None, head]
        while lis[-1].next:
            lis.append(lis[-1].next)
        while m <= n:
            lis[m].val, lis[n].val = lis[n].val, lis[m].val
            m += 1
            n -= 1
        return head

编辑于 2023-09-08 19:58:00 回复(2)

Python3

Vivimore

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        res = ListNode(-1)
        res.next = head
        pre = res
        cur = head
        for i in range(1, m):
            pre = cur
            cur = cur.next
        for i in range(m, n):
            temp = cur.next
            cur.next = temp.next
            temp.next = pre.next
            pre.next = temp
        return res.next

好难想明白啊

发表于 2022-05-13 19:44:10 回复(4)