一媚媒、題目

給出一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)涩僻，并返回翻轉(zhuǎn)后的鏈表。

k 是一個(gè)正整數(shù)逆日，它的值小于或等于鏈表的長(zhǎng)度嵌巷。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么將最后剩余節(jié)點(diǎn)保持原有順序室抽。

示例 :

給定這個(gè)鏈表：1->2->3->4->5

當(dāng) k = 2 時(shí)搪哪，應(yīng)當(dāng)返回: 2->1->4->3->5

當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: 3->2->1->4->5

說明 :
你的算法只能使用常數(shù)的額外空間坪圾。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值晓折，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換惑朦。

二、解題

創(chuàng)建四個(gè)指針漓概，分別為p=head和q=head?.next行嗤，p的k個(gè)節(jié)點(diǎn)的尾部pTail=nil，q的頭部qHead=head垛耳。
使用while遍歷鏈表,同時(shí)使用i計(jì)數(shù),移動(dòng)指針q栅屏，將q移動(dòng)到p的頭部。當(dāng)i==k時(shí)堂鲜，如果pTail不為空栈雳，將將p添加到pTail后面，同時(shí)記錄當(dāng)前的p的尾部pTail和q的頭部qHead缔莲。并將p和q向后移動(dòng)到下一組節(jié)點(diǎn)哥纫。之后需要處理一個(gè)額外情況，當(dāng)剩下的節(jié)點(diǎn)不足k個(gè)時(shí)痴奏，需要將之后的節(jié)點(diǎn)在翻轉(zhuǎn)會(huì)原樣蛀骇。
時(shí)間復(fù)雜度為O(n)。

步驟

三读拆、代碼實(shí)現(xiàn)

    class Solution {
        func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
            if head == nil || k == 0{
                return head;
            }
            var result: ListNode? = nil;
            var preTail: ListNode? = nil;
            var currentTail: ListNode? = head;
            
            var p,q,r: ListNode?
            p = head
            q = head?.next;
            p?.next = nil
            var i = 1
            while q != nil {
                r = q?.next;
                q?.next = p;
                p = q
                q = r
                i += 1
                if i == k {
                    if result == nil {
                        result = p
                    }
                    
                    if preTail != nil {
                        preTail?.next = p;
                    }
                    preTail = currentTail;
                    currentTail = q
                    
                    if q != nil {
                        p = q;
                        q = q?.next;
                    }
                    currentTail?.next = nil;
                    i = 1
                }
            }
            if currentTail != nil {
                q = p?.next
                p?.next = nil
                while q != nil {
                    r = q?.next
                    q?.next = p;
                    p = q;
                    q = r;
                }
                preTail?.next = currentTail
            }
            if result == nil {
                result = p
            }
            return result
        }
    }

Demo地址：github