首页 > 试题广场 >

链表内指定区间反转

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

热度指数：409512 时间限制：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

物理魔理沙Kiri

class Solution:
    def reverseBetween(self , head: ListNode, m: int, n: int) -> ListNode:
        firstNode = ListNode(None)
        lastNode = ListNode(None)
        r = head
        while 1:
            if r.next == None:
                r.next = lastNode
                lastNode = r
                break
            else:
                r = r.next
        firstNode.next = head
        begin = firstNode
        head = firstNode
        revnums = n - m
        while m > 1:
            begin = begin.next
            m -= 1
        r = begin.next
        p = begin.next.next
        q = p.next
        while revnums > 0:
            p.next = begin.next
            begin.next = p
            r.next = q
            p = q
            q = q.next
            revnums -= 1
        while 1:
            if r.next.val == None:
                r.next = None
                break
            else:
                r = r.next
        return head.next

这是我的方法，链表加上头尾节点，这样使得每一个有数据的节点都有前驱和后继，然后通过头插法判断。

这个方法还不够完善，通过AI修改过的代码如下：

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # 创建虚拟头节点，简化边界条件处理
        dummy = ListNode(None)
        dummy.next = head
        prev = dummy  # prev 指向区间的前一个节点

        # 找到区间的前一个节点
        for _ in range(m - 1):
            prev = prev.next

        # 反转区间内的节点
        curr = prev.next  # curr 指向区间的第一个节点
        next_node = curr.next  # next_node 指向 curr 的下一个节点

        # 使用节点状态判断控制循环
        while next_node and m < n:
            curr.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node
            next_node = curr.next
            m += 1

        return dummy.next

AI优化了我的程序。
这道题的关键，主要是发现在原链表反转区间内，反转前的第一个节点，会变到最后，而在反转过程中，由于next指针变化，将导致反转区间的下一个节点出现断连。

我认为，一个链表有头尾节点，会很好的简化操作，因为头尾节点可以保证每一个保存数据的节点都必然有前驱和后继。

发表于 2025-03-09 10:28:54 回复(0)

Python3

牛客517034011号

from os import preadv
# 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
        #添加一个不变的节点
        X_Node=ListNode(0)
        X_Node.next=head
        
        node_m=X_Node
        
        #获取头部最后一个不变的节点
        i=0
        if n==m:
            return head
        while i<m-1:
            node_m=node_m.next
            i+=1

       #获取尾部第一个不变的节点
        i=0
        node_n=head
        while i<n-1:
            node_n=node_n.next
            i+=1
        node_n_n=node_n.next

        #翻转
        for i in range(m,n):
            temp=node_m.next #临时存储变更的节点
            node_m.next=temp.next #将下一个节点向前
            node_n.next=temp #变动的节点放再最后一个变动节点的尾部
            temp.next=node_n_n #连接不变的节点
            node_n_n=temp #更新不会变动的尾部节点

        return X_Node.next

发表于 2025-02-20 01:47:45 回复(0)

Python3

牛客909652776号

# 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:

firstNode = ListNode(-1) # 创建一个辅助节点，作为初始节点

firEnd = firstNode

for i in range(0,m-1):# 从位置1到位置m-1不进行翻转

firEnd.next = head

firEnd = firEnd.next

head = head.next

secStart = None

secEnd = head

for i in range(0,n-m+1): # 从位置m到n,需要进行翻转

cur = head

head = head.next

cur.next=secStart

secStart = cur

firEnd.next = secStart

secEnd.next = head

return firstNode.next

发表于 2024-12-21 19:03:14 回复(0)

Python3

为谁疯狂

# 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
        if head == None:
            return head
        a = ListNode(0)
        count, j = 1, -1
        li = []
        li1 = []
        p1= head
        for i in range(1,n+1): #将单链表需反转数据赋给列表1
            if i >= m:
                li1.append(p1.val)
            p1 = p1.next
        while head != None: #将反转与不反转的数据整合至一个列表中
            p = head
            head = p.next
            p.next = a.next
            if count >= m and count <= n:   # 将反转数据按排序后一一赋值
                p.val = li1[j]
                j = j - 1
            li.append(p.val)    # 将所有数据一一放进列表中
            count = count + 1
        New_head = ListNode(li[0])  #头节点
        cur = New_head      #指针指向头节点
        for i in li[1:]:    # 将列表排好数据转换为单链表
            node = ListNode(i)
            cur.next = node # 将列表数据赋给单链表下一个
            cur = cur.next
        return New_head

发表于 2024-09-13 12:02:05 回复(0)

Python3

想顺利就职的比尔在发呆

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if m == n:
            return head
        little,big = min(m, n),max(m, n)
        record_List = []
        while head != None:
            record_List.append(head)
            head = head.next        
        s,l = (big-little+1)//2, len(record_List)       
        for i in range(s):
            record_List[little-1+i],record_List[big-1-i] = record_List[big-1-i],record_List[little-1+i]
        for i in range(l):
            if i < l-1:
                record_List[i].next = record_List[i+1]
            else:
                record_List[i].next = None
        return record_List[0]

发表于 2024-08-07 15:20:57 回复(0)

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)