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

對于一個鏈表帖努，你首先要進(jìn)行判斷，長度是不是大于等于K啊粪般，不然這種無中生有的問題拼余，你在幫他說一遍，你等于亩歹，你也責(zé)任吧匙监？
正題：還是基于遞歸來一個非常簡單的思想： head 是一個鏈表的頭部引用，首先判斷： head 是不是None啊小作，head這個鏈表長度是不是大于k啊亭姥，如果是，那我就什么也不做直接返回顾稀，這是墜吼的达罗。
如果鏈表長度滿足大于等于k,那我就把前k個節(jié)點翻轉(zhuǎn)，得到一個新的頭和尾，返回新的頭粮揉。新的尾.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

表現(xiàn)

類似：

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
        

很傻侨拦。。