25.md

25. Reverse Nodes in k-Group

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.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For 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

my thoughts:

1. use a pseudo head, p1, put gap k between p1 and p2; if p2, keep move p2 down while reverse p1-p2 by 1. hold p1.next.next in p4; 2. set p1.next.next as p2.next; 3. insert p4 between p1 and p1.next; 4. move p4 to p4.next; repeat 3&4 k-1 times

my solution:

**********69ms
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k<2:
            return head
        
        pse = ListNode(-1)
        pse.next = head
        p1 = pse
        p2 = p1.next
        i = k
        while p2 and i>1:
            p2 = p2.next
            i -= 1
        while p2:
            #print p2.val, p1.val
            p2 = p2.next            
            nexthead = p3 = p1.next
            p4 = p3.next
            p3.next = p2
            i = 1
            while i<k:
                p1.next = p4
                p4 = p4.next
                p1.next.next = p3
                p3 = p1.next
                if p2:
                    #print 'inner', p2.val, p1.val, p3.val, p4.val
                    p2 = p2.next
                i += 1
            p1 = nexthead
        return pse.next

my comments:

need to remember how to reverse a linked list:
	#reverse in group
	prev,new = None,head
	for i in xrange(k):
		t=new.next
		new.next = prev
		prev = new
		new = t

from other ppl's solution:

1. nice recursion, 62ms:
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # edge cases
        if not head or not head.next or k<2: return head
        # go to the k-1 position: think about if k==1
        res = head
        for _ in xrange(k-1):
            res = res.next
            if not res: return head
            
        #reverse in group
        prev,new = None,head
        for i in xrange(k):
            t=new.next
            new.next = prev
            prev = new
            new = t
            
        # apply recursion for next group
        # the original head now is the tail
        head.next = self.reverseKGroup(new,k)
        return res
		
2. very intuitive and readable, 55ms:
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or k <= 1:
            return head
        dummy = ListNode(0)
        dummy.next = head
        
        prev = dummy
        count = 0
        cur = head
        while cur != None:
            count += 1
            cur = cur.next
            if count == k:
                prev = self.reverse(prev, cur) 
                count = 0
        return dummy.next
    
    def reverse(self, prev, end): # Exclusive
        cur = prev.next # inclusive starat
        while cur.next != end: 
            next = cur.next
            cur.next = next.next
            next.next = prev.next
            prev.next = next
        return cur