题解 | #链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
package main import . "nc_tools" func reverseBetween(head *ListNode, m int, n int) *ListNode { if head == nil || head.Next == nil || m >= n { return head } final := &ListNode{-1, head} // 哑节点 start := final // 开始翻转的节点的前一个节点 // 找开始翻转的节点的前一个节点 for i := 0; i < m-1; i++ { if start.Next == nil { return head // 如果 m 大于链表长度,直接返回原链表 } start = start.Next } end := start.Next // 开始翻转的节点 // 找结束节点(即反转后链表的最后一个节点的下一个节点) for i := 0; i < n-m; i++ { if end == nil { return head // 如果 n 大于链表长度,直接返回原链表 } end = end.Next } // 保存要反转的节点头部节点 leftNode := start.Next // 断开 start 和 end 后的链表 nextNode := end.Next start.Next = nil end.Next = nil // 开始翻转 pre := &ListNode{} cur := leftNode for cur != nil { temp := cur.Next cur.Next = pre pre = cur cur = temp } // 接起来 start.Next = pre // pre 现在是翻转后子链表的头部节点 leftNode.Next = nextNode // 翻转前子链表的最后一个节点连接到翻转后的子链表之后的节点 return final.Next // 返回新链表的头节点 } // ... 其他代码 ...