【算法日?！縆個(gè)一組反轉(zhuǎn)鏈表

K個(gè)一組翻轉(zhuǎn)鏈表

題目來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

給你一個(gè)鏈表，每?k?個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(zhuǎn)后的鏈表。

k?是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度。

如果節(jié)點(diǎn)總數(shù)不是?k?的整數(shù)倍，那么請(qǐng)將最后剩余的節(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

說(shuō)明 :

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

題解

1.鏈表需要翻轉(zhuǎn)的每k個(gè)長(zhǎng)度的子鏈表看做是一個(gè)整體，就是一個(gè)反轉(zhuǎn)鏈表的問(wèn)題。
2.剩下需要關(guān)心的就是將翻轉(zhuǎn)后的子鏈表 連接到總鏈表上，所以需要找出 需要反轉(zhuǎn)的子鏈表的 前面的節(jié)點(diǎn)，后面的節(jié)點(diǎn)，和需要反轉(zhuǎn)的鏈表的開(kāi)始的節(jié)點(diǎn)和結(jié)束的節(jié)點(diǎn)。
3.反轉(zhuǎn)動(dòng)作結(jié)束后 ，將反轉(zhuǎn)鏈表的前面的節(jié)點(diǎn)連接到反轉(zhuǎn)后的鏈表的開(kāi)始位置，將反轉(zhuǎn)后的結(jié)束位置節(jié)點(diǎn) 連接 到本組需要反轉(zhuǎn)鏈表后面的節(jié)點(diǎn)，這樣本次反轉(zhuǎn)就完成了。依次類推直至需要反轉(zhuǎn)的鏈表的長(zhǎng)度小于k，完成了k個(gè)一組反轉(zhuǎn)鏈表的操作了
時(shí)間復(fù)雜度為 O(n), 空間復(fù)雜度為 O(1)

代碼如下:

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-13
# @File     : reverse_nodes_k_group.py
# Software  : study

"""
K 個(gè)一組翻轉(zhuǎn)鏈表
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverse_list(head: ListNode) -> ListNode:
    new_node = None
    while head:
        p = head.next          # 暫存下一個(gè)節(jié)點(diǎn)
        head.next = new_node   # head指向上一個(gè)節(jié)點(diǎn) 上一個(gè)節(jié)點(diǎn)是從None開(kāi)始
        new_node = head        # new_node 向后移動(dòng)到當(dāng)前head位置
        head = p               # head 向后移動(dòng)一個(gè)節(jié)點(diǎn)
    if not new_node:
        return head
    else:
        return new_node

def reverse_k_group(head: ListNode, k: int) -> ListNode:
    if head and head.next:
        pre = ListNode(0)
        pre.next = head                         # 申請(qǐng)一個(gè)新的節(jié)點(diǎn)，記錄最開(kāi)始的位置，為了最后返回翻轉(zhuǎn)后的第一個(gè)節(jié)點(diǎn)
        tmp = pre
        while tmp and tmp.next:
            i = 1
            start = end = tmp.next              # 申請(qǐng)開(kāi)始和結(jié)束指針，初始化本組需要翻轉(zhuǎn)鏈表的頭節(jié)點(diǎn)位置
            while i < k and end.next:           # 本循環(huán)的作用是將end指針指向 本組需要翻轉(zhuǎn)鏈表的最后一個(gè)位置
                end = end.next
                i += 1
            if i == k:                          # 若本組需要翻轉(zhuǎn)鏈表的長(zhǎng)度符合k，就進(jìn)行下去
                last = end.next                 # last 記錄本組需要翻轉(zhuǎn)鏈表的后面的頭節(jié)點(diǎn)位置
                end.next = None                 # 將本組需要翻轉(zhuǎn)你鏈表的最后一個(gè)節(jié)點(diǎn)的next置為None，方便翻轉(zhuǎn)
                tmp.next = reverse_list(start)  # 返回交換后鏈表的頭節(jié)點(diǎn)，使 本組需要翻轉(zhuǎn)鏈表 的前面鏈表的最后節(jié)點(diǎn)的next指向翻轉(zhuǎn)后的頭節(jié)點(diǎn)
                start.next = last               # 將翻轉(zhuǎn)后的最后一個(gè)節(jié)點(diǎn)的next指針指向 本組翻轉(zhuǎn)鏈表后面的節(jié)點(diǎn) ，  這樣翻轉(zhuǎn)后的鏈表就和原來(lái)的鏈表連接上了

                tmp = start                     # 將tmp指針指向下一組需要翻轉(zhuǎn)鏈表 的前面的節(jié)點(diǎn)
            else:                               # 若本組鏈表長(zhǎng)度不符合k，即不進(jìn)行交換，說(shuō)明已經(jīng)全部交換完成，返回交換后頭節(jié)點(diǎn)
                return pre.next
        return pre.next
    else:
        return head

if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    k = 2

    res = reverse_k_group(node1, k)
    while res:
        print(res.val)
        res = res.next

輸出結(jié)果：

2
1
4
3
5