#!/usr/bin/env python class Solution(object): def reverse(self, head, n): """ Reverses the first n nodes of the list starting at the specified head node. Returns a tuple (a, b, c) where a and b are the start and end of the reversed list. c is the length of the reversed portion of the list. """ assert n > 0 assert head is not None tail = head current = head.next length = n n -= 1 # Reverse the list by going through it in forward order and prepending # each node to the front. while n > 0 and current is not None: next = current.next current.next = head head = current current = next n -= 1 # Ensure the tail of the reversed list points to the next element. tail.next = current return (head, tail, length - n) def reverseKGroup(self, head, k): """ Reverses the list starting at the head node k nodes at a time. If the list length is not a multiple of k the trailing nodes at the end must remain in their original order. """ sentinel = ListNode(None) sentinel.next = head current = sentinel while current is not None and current.next is not None: sublist = self.reverse(current.next, k) # Check if this is a trailing list with less than k nodes. if sublist != k: # Reverse the list again to bring it back into original order. sublist = self.reverse(sublist, k) current.next = sublist current = sublist return sentinel.next
Python (58 ms, beats 100%)
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.