Question

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

Subscribe to see which companies asked this question.

Thinking

对于一个链表，你首先要进行判断，长度是不是大于等于K啊，不然这种无中生有的问题，你在帮他说一遍，你等于，你也责任吧？
正题：还是基于递归来一个非常简单的思想： head 是一个链表的头部引用，首先判断： head 是不是None啊，head这个链表长度是不是大于k啊，如果是，那我就什么也不做直接返回，这是坠吼的。
如果链表长度满足大于等于k,那我就把前k个节点翻转，得到一个新的头和尾，返回新的头。新的尾.next = 链表剩下部分做一样事情返回的新头。 然后递归。。

Code

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

class Solution(object):
    def LenOfList(self, li):
        cnt = 0
        p = li
        while p is not None:
            cnt += 1
            p = p.next
        return cnt

    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        size = self.LenOfList(head)
        if size < k or size == 1:
            return head
        else:
            new_tail = head
            # since the size(head) >= k,reverse k elements in the list
            cnt = 1
            p1 = head
            p2 = head.next
            while cnt < k:
                cnt += 1
                tmp = p2.next
                p2.next = p1
                p1 = p2
                p2 = tmp
            new_tail.next = self.reverseKGroup(p2, k)
        return p1

Performance

表现

类似：

27. Remove Element

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        size = len(nums)
        cnt = 0
        for i in range(size):
            if nums[i] == val:
                nums[i] = '#'
            else:
                cnt += 1
        nums.sort()
        nums = nums[0:cnt]
        return cnt
        

很傻。。