Question: http://oj.leetcode.com/problems/reverse-nodes-in-k-group/
Question Name: Reverse Nodes in k-Group
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # @param pre, a ListNode # @param current, a ListNode # @param k, an integer # @return a ListNode def _reverseNextK(self, pre, current, k): # Not enough nodes to reverse if current == None: return None, None # Last node to reverse if k == 1: nextNode = current.next current.next = pre return current, nextNode # Recursively reverse the remaining nodes newHead, nextHead = self._reverseNextK(current, current.next, k-1) if newHead == None: # Not enough nodes to reverse return None, None else: # Reversing current.next = pre return newHead, nextHead # @param head, a ListNode # @param k, an integer # @return a ListNode def reverseKGroup(self, head, k): newHead, nextHead = self._reverseNextK(None, head, k) if newHead == None: return head # Not enough nodes to reverse else: result = newHead # Record the new head node preTail = head # As long as there are enough nodes to reverse, do it. while nextHead != None: currentNode = nextHead # Reverse the nodes inside the next K-group newHead, nextHead = self._reverseNextK(None, currentNode, k) if newHead != None: preTail.next = newHead # Reversed else: preTail.next = currentNode # Not reversed preTail = currentNode return result |