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

思路

先判断是否有k个节点，如果有，则将这k个节点逆序，否者返回，重要的是上一步的尾节点和下一步的头结点要对接上，同leetcode24

Python实现

# 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==1 or head==None:
            return head
        i=1
        h=head
        while i<k:
            if h.next!=None:h=h.next
            else:return head
            i+=1
        endp=None
        while head!=None:
            phead=head
            i=1
            while i<k:
                if head.next!=None :
                    head=head.next
                else:
                    endp.next=phead
                    return h
                i+=1
            if endp!=None:endp.next=head
            head=phead
            endp=head
            pre=head
            head=head.next
            i=1
            while i<k:
                p=head
                head=p.next
                p.next=pre
                pre=p
                p=head
                i+=1
        endp.next=None
        return h