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

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

很傻。。