Leetcode 25. Reverse Nodes in k-Group with Python

문제

Given the head of a linked list, 
reverse the nodes of the list k at a time, 
and return the modified list.

k is a positive integer and 
is less than or equal to the length of the linked list.
If the number of nodes is not a multiple of k then left-out nodes, 
in the end, should remain as it is.

You may not alter the values in the list's nodes, 
only nodes themselves may be changed.

연결리스트의 헤드가 주어진다,
k개씩 묶어 링크드 리스트를 거꾸로 만든 뒤 리턴하시오.
k는 링크드 리스트의 길이와 같거나 짧은 양의 정수이다.

예시

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

제한

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

풀이법

링크드 리스트를 거꾸로 뒤집는다.

from typing import List, Optional

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        
        if k == 1: return head
        
        length = 0
        c = head
        while c != None:
            length += 1
            c = c.next
        
        c = head
        prev = None
        
        first = True
        
        while length >= k:
            if first:
                l: List[ListNode] = []
                for _ in range(k):
                    l.append(c)
                    c = c.next
                    length -= 1
                l.reverse()
                for index in range(len(l)-1):
                    l[index].next = l[index+1]
                l[len(l)-1].next = c
                first = False
                head = l[0]
                prev = l[len(l)-1]
            else:
                l: List[ListNode] = []
                for _ in range(k):
                    l.append(c)
                    c = c.next
                    length -= 1
                l.reverse()
                prev.next = l[0]
                prev = l[len(l)-1]
                for index in range(len(l)-1):
                    l[index].next = l[index+1]
                l[len(l)-1].next = c
            
        return head