首页 > itarticle > leetcode25-reverse nodes in k-group

leetcode25-reverse nodes in k-group

admin 11月 12, 2020 0

题目

交换链表中相邻的k个数
举例：
输入：a->b->c->d,k=3
输出：c->b->a->d

分析

对于k=3的情况

-1(pre) -> 1(cur) -> 2(nex) -> 3 -> 4 -> 5

-1(pre) -> 2 -> 1(cur) -> 3(nex) -> 4 -> 5

-1(pre) -> 3 -> 2 -> 1(cur) -> 4(nex) -> 5

始终是：

for i in range(k-1)
    tmp = pre.next
    pre.next = cur.next
    cur.next = nex.next
    nex.next = tmp
    nex = cur.next

python代码实现

class (object):

    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or k == 1:
            return head
        pre = ListNode(0)
        pre.next = head
        res = cur = nex = tmp = pre
        count = 0
        while(cur.next):
            count += 1
            if count == k:
                cur = pre.next
                nex = cur.next
                for i in range(k-1):
                    tmp = pre.next
                    pre.next = cur.next
                    cur.next = nex.next
                    nex.next = tmp
                    nex = cur.next
                count = 0
                pre = cur
            cur = cur.next
        return res.next