题目
翻转链表
问题:
翻转链表中第 m 个节点到第 n 个节点的部分
说明:
m,n 满足 1 ≤ m ≤ n ≤ 链表长度
示例:
示例 1:
输入: 1->2->3->4->5->null, m = 2 和 n = 4
输出: 1->4->3->2->5->null
解题思路:
首先我们在头节点前面插入一个 dummy 节点, 那样头节点就可以看作中间节点了, 不需要额外考虑其他情况了. 然后就是交换两个相邻节点之间的 next 指针了, 这一步需要记录三个节点的信息
代码:
- /**
- public class SingNode {
- public var value : Int
- public var nextNode: SingNode?
- public init(value:Int) {
- self.value = value
- }
- }
- extension SingNode : CustomStringConvertible {
- public var description: String {
- var string = "\(value)"
- var node = self.nextNode
- while node != nil {
- string = string + "--" + "\(node!.value)"
- node = node?.nextNode
- }
- return string
- }
- }
- **/
- func reverseBetween(_ l1:SingNode?, m:Int,n:Int) -> SingNode? {
- if l1 == nil {
- return l1
- }
- let dummyNode = SingNode.init(value: 0)
- dummyNode.nextNode = l1
- var headNode = dummyNode
- var preNode = dummyNode
- for _ in 0 ..< m {
- preNode = headNode
- headNode = headNode.nextNode!
- }
- for _ in m ..< n {
- let temp = headNode.nextNode
- headNode.nextNode = temp?.nextNode
- temp?.nextNode = preNode.nextNode
- preNode.nextNode = temp
- }
- return dummyNode.nextNode
- }
来源: http://www.jianshu.com/p/252aed6d6343