Given a linked list, reverse the nodes of a linked list k at a time and return its 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.




Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:


       Only constant extra memory is allowed.
       You may not alter the values in the list's nodes, only nodes itself may be changed.

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        

Solutions:
# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def kth(self, v, k):
         for i in range(k-1):
             if not v:
                 return None
             v=v.next
         return v
     
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         if k==1:
             return head
         kthnode=self.kth(head, k)
         v=head
         head=kthnode if kthnode else head
         i=0
         tmphead=v
         while kthnode:
             vprev=kthnode.next
             for i in range(k):
                 v.next, v, vprev = vprev, v.next, v
                 kthnode=None if not kthnode else kthnode.next
             tmphead.next=kthnode if kthnode else v
             tmphead=v
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         if head == None:
             return None
         if head.next == None:
             return head
         
         cur = head
         prev = None
         count = 0
         if self.getsize(cur) >= k:
             while count < k and cur != None:
                 temp = cur
                 cur = cur.next
                 temp.next = prev
                 prev = temp
                 count = count + 1
             if cur != None:
                 head.next = self.reverseKGroup(cur, k)
             return prev
         
         return cur
                 
         
     def getsize(self, head):
         curnode = head
         count = 0
         while curnode != None:
             curnode = curnode.next
             count = count + 1
         return count
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverse(self, start, end):
         head = ListNode(0)
         head.next = start
         while head.next != end:
             temp = start.next
             start.next = temp.next
             temp.next = head.next
             head.next = temp
         return [end, start]
     
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         if head is None or head.next is None:
             return head
         dummpy = ListNode(0)
         dummpy.next = head
         phead = dummpy
         while phead.next:
             start, end = phead.next, phead.next
             for i in range(k-1):
                 end = end.next
                 if end is None:
                     return dummpy.next
             result = self.reverse(start, end)
             phead.next = result[0]
             phead = result[1]
         return dummpy.next
             

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverse(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         counter = k
         tail = head
         prev = None
         current = head
         
         while counter > 0 and current:
             newCurrent = current.next
             current.next = prev
             prev = current
             current = newCurrent
             counter -= 1
         
         if counter > 0:
             return self.reverse(prev, k - counter)
         
         head = prev
             
         return (head, tail, current)
     
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         if k == 0:
             return head
         
         head, tail, current = self.reverse(head, k)
         while current:
             joinedFragmentHead, newTail, newCurrent = self.reverse(current, k)
             tail.next = joinedFragmentHead
             tail = newTail
             current = newCurrent
             
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         current = head 
         next  = None
         prev = None
         count = 0
         
         if(self.nextkthnode(head,k) is None):
             return head
         while(current is not None and count < k):
             next = current.next
             current.next = prev
             prev = current
             current = next
             count += 1
  
        
         if next is not None and self.nextkthnode(next,k) is not None:
             head.next = self.reverseKGroup(next, k)
         elif(next is not None):
             head.next = next
  
         return prev 
             
         
     def nextkthnode(self, head, k):
         for i in range(k-1):
             if(head==None):
                 return None
             head=head.next
         return head

# Definition for singly-linked list.
 class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None
 
 class Solution:
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
 
         copy = head
         for _ in range(k):
             if copy is None:
                 return head
             else:
                 copy = copy.next
 
         k_nodes = []
         for _ in range(k):
             k_nodes.append(head)
             head = head.next
         rest = k_nodes[-1].next
 
         for i in reversed(range(1, len(k_nodes))):
             k_nodes[i].next = k_nodes[i-1]
         k_nodes[0].next = self.reverseKGroup(rest, k)
 
         return k_nodes[-1]
 


# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         if head == None:
             return None
         if k == 1:
             return head
         res = []
         while(head!=None):
             res.append(head.val)
             head = head.next
         lens = len(res)
         res1 = []
         start = 0
         while(start+k <= lens):
             b = res[start:start+k]
             c = list(reversed(b))
             res1 += c
             start += k
         b = res[start:lens]
         res1 += b
         return res1
         
         

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         previous_node, current_node = None, head
         ret = self.getKElem(head, k - 1)
         if not ret: return head
         last = ret
         while last:
             if previous_node: previous_node.next = last
             for _ in range(k):
                 next_node = current_node.next
                 current_node.next = previous_node
                 current_node, previous_node = next_node, current_node
             previous_node = head
             previous_node.next = current_node
             head = current_node
             last = self.getKElem(head, k - 1)
         
         return ret
     
     def getKElem(self, head, k):
         if k < 0: return None
         while k > 0:
             if not head: return None
             k -= 1
             head = head.next
         return head

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         root = p = ListNode(0);
         flag = 0
         while head:
             tlist = []
             for i in range(k):
                 if head != None:
                     tlist.append(head.val);
                     head = head.next;
                 else:
                     flag = 1;
                     break;
             if flag == 0:
                 for i in range(k):
                     p.next = ListNode(tlist[k-1-i]);
                     p = p.next;
             else:
                 for i in tlist:
                     p.next = ListNode(i);
                     p = p.next;
         return root.next

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reverseK(self, beg, end):        
         prev = None
         curr = beg
         while curr is not end:
             next_node = curr.next
             curr.next = prev
             prev = curr
             
             curr = next_node
             
         return prev, beg
             
         
     def reverseKGroup(self, head, k):
         """
         :type head: ListNode
         :type k: int
         :rtype: ListNode
         """
         if head is None:
             return None
         
         fake = ListNode(0)
         prev = fake
         curr = head
         
         while curr:
             i = 1
             tail = curr
             while i <= k and tail:
                 tail = tail.next
                 i += 1
             
             if i -1 == k:
                 new_curr = tail
                 r_head, r_tail = self.reverseK(curr, tail)
             else:
                 r_head = curr
                 r_tail = None
                 new_curr = None
             
             curr = new_curr
             prev.next = r_head
             
             if r_tail:
                 r_tail.next = curr
                 
             prev = r_tail
             
         return fake.next        

class Solution:
     def reverseKGroup(self, head, k):
         if not head:
             return head
 
         cur = head
 
         for _ in range(k - 1):
             cur = cur.next
             if not cur:
                 return head
 
         prev = self.reverseKGroup(cur.next, k)
         cur.next = None
         cur = head
 
         while cur:
             temp = cur.next
             cur.next = prev
             prev, cur = cur, temp
 
         return prev

"""
 3->2->1->6->5->4
 
 """
 
 # Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 #return (head, tail)
 def reverse_LL2(node, length):
     if length == 1:
         return (node, node)
     back = None
     curr = node
     forward = node.next
     for _ in range(length):
         curr.next = back
         back = curr
         curr = forward
         if forward:
             forward = forward.next
     return (back, node)
 
 def reverse_LL(node, length):
     if length == 1:
         return node
     rest = node.next
     restR = reverse_LL(rest, length - 1)
     rest.next = node
     node.next = None
     return restR
     
     
 def jump_LL(node, length):
     curr = node
     for _ in range(length):
         if curr == None:
             return False
         curr = curr.next
     return curr
 
 class Solution:
     def reverseKGroup(self, head, k):
         if (head == None):
             return None
         jumped = jump_LL(head, k)
         if jumped == False:
             return head
         rev = reverse_LL(head, k)
         head.next = self.reverseKGroup(jumped, k)
         return rev