目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
链表内指定区间反转
访问量:1219
一、简介
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。
给出的链表为 1 => 2 => 3 =>4 => 5 => NULL,m=2,n=4
返回 返回 1→4→3→2→5→NULL
二、实现
思路:找到待翻转的起点,从起点开始翻转即可,需要注意起点可能是头指针。
func reverseBetween( head *ListNode , m int , n int ) *ListNode { // write code here if head == nil { return nil } // 不需要翻转 if m == n { return head } // 起点为头指针 if m == 1 { return reverseStart(head, n - m) } var ( parentNode = head startNode = head ) i := 1 for m > i && startNode != nil{ parentNode = startNode startNode = startNode.Next i++ } parentNode.Next = reverseStart(startNode, n - m) return head } // 从头节点开始翻转n个节点 func reverseStart(p *ListNode, n int) *ListNode{ var ( newHead *ListNode nextNode *ListNode ) oldHead := p for p != nil && n >= 0 { nextNode = p.Next p.Next = newHead newHead = p p = nextNode n -- } oldHead.Next = nextNode return newHead }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助