LeetCode算法题-25. K 个一组翻转链表（Swift）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

方法1-遍历链表，每k个存数组。然后拼接

   func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        
        let resultNode = ListNode(0)
        var currentNode = resultNode

        var headNode = head

        while headNode != nil {
            
            var nodeArr = [ListNode]()
            for _ in 0..<k {
               
                if headNode != nil {
                                    
                    let currentHeadNode = headNode
                    nodeArr.append(currentHeadNode!)
                    headNode = headNode!.next
                }
            }
            if nodeArr.count == k {
                
                for i in (0...k-1).reversed() {
                                           
                    nodeArr[i].next = nil
                    currentNode.next = nodeArr[i]
                    currentNode = currentNode.next!
                }
            }else if nodeArr.count > 0{
                
                currentNode.next = nodeArr[0]
            }
        }
        return resultNode.next
    }

这个方法空间复杂度不为1，具体是多少，我不会算，跟k有关吧？每次循环，都会开辟k个数组空间。如果有大神会，可以解释一下~

方法2-将链表拆成 k个节点为一组的链表，逆转此段链表，不存数组

func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
          
        
        let resultNode = ListNode(0)
        resultNode.next = head
        
        var preNode: ListNode?  = resultNode
        var endNode: ListNode? = resultNode
        
        while endNode?.next != nil {
            
            var index = 0
            while index < k && endNode != nil {
                
                endNode = endNode?.next
                index += 1
            }
            
            //如果<k,不交换
            if endNode == nil {
                break
            }
            
            //这一段链表的开始，交换后，就变成这一段链表的结束，下一段链表的preNode
            let start = preNode?.next
            
            //记录下个链表的开始。
            let next = endNode?.next
            endNode?.next = nil
            
            //start - end节点 这一段链表逆序
            //
            preNode?.next = reverse(start)
            start?.next = next
            preNode = start
            endNode = preNode
            
        }
        
        return resultNode.next
    }
    func reverse(_ head: ListNode?) -> ListNode?{
        
        let resultNode = ListNode(0)
        
        var curNode = head
        while curNode != nil {
            
            let next = curNode?.next
            curNode?.next = resultNode.next
            resultNode.next = curNode
            curNode = next
        }
        
        return resultNode.next
    }