【算法日常】K個一組反轉鏈表

K個一組翻轉鏈表

題目來源：力扣（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個長度的子鏈表看做是一個整體，就是一個反轉鏈表的問題。
2.剩下需要關心的就是將翻轉后的子鏈表 連接到總鏈表上，所以需要找出 需要反轉的子鏈表的 前面的節點，后面的節點，和需要反轉的鏈表的開始的節點和結束的節點。
3.反轉動作結束后 ，將反轉鏈表的前面的節點連接到反轉后的鏈表的開始位置，將反轉后的結束位置節點 連接 到本組需要反轉鏈表后面的節點，這樣本次反轉就完成了。依次類推直至需要反轉的鏈表的長度小于k，完成了k個一組反轉鏈表的操作了
時間復雜度為 O(n), 空間復雜度為 O(1)

代碼如下:

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

"""
K 個一組翻轉鏈表
"""

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          # 暫存下一個節點
        head.next = new_node   # head指向上一個節點 上一個節點是從None開始
        new_node = head        # new_node 向后移動到當前head位置
        head = p               # head 向后移動一個節點
    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                         # 申請一個新的節點，記錄最開始的位置，為了最后返回翻轉后的第一個節點
        tmp = pre
        while tmp and tmp.next:
            i = 1
            start = end = tmp.next              # 申請開始和結束指針，初始化本組需要翻轉鏈表的頭節點位置
            while i < k and end.next:           # 本循環的作用是將end指針指向 本組需要翻轉鏈表的最后一個位置
                end = end.next
                i += 1
            if i == k:                          # 若本組需要翻轉鏈表的長度符合k，就進行下去
                last = end.next                 # last 記錄本組需要翻轉鏈表的后面的頭節點位置
                end.next = None                 # 將本組需要翻轉你鏈表的最后一個節點的next置為None，方便翻轉
                tmp.next = reverse_list(start)  # 返回交換后鏈表的頭節點，使 本組需要翻轉鏈表 的前面鏈表的最后節點的next指向翻轉后的頭節點
                start.next = last               # 將翻轉后的最后一個節點的next指針指向 本組翻轉鏈表后面的節點 ，  這樣翻轉后的鏈表就和原來的鏈表連接上了

                tmp = start                     # 將tmp指針指向下一組需要翻轉鏈表 的前面的節點
            else:                               # 若本組鏈表長度不符合k，即不進行交換，說明已經全部交換完成，返回交換后頭節點
                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

輸出結果：

2
1
4
3
5