>

自由软件精神——“自由、开放、分享”。自由软件自诞生之日起,就秉承了学术自由的思想,信奉科学无国界,知识应该全人类共享。

ubuntu精神——人道待人,天下共享连接人人的信念。具有 ubuntu 精神的人心胸开阔,乐于助人,见贤思齐而不忌妒贤能......

leetcode刷题 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.

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

__author__ = 'bone-lee'

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

class Solution:
    # @param head, a ListNode
    # @param k, an integer
    # @return a ListNode
    def reverseKGroup(self, head, k):
        if head is None: return None
        assert k>0
        pre=node=head
        new_head=tail_tmp=None
        left_node=None
        n=0
        while node:
            next_node=node.next
            n+=1
            if n%k==0:
                self.reverse(pre,node)
                if not new_head:
                    new_head=node
                if tail_tmp:
                    tail_tmp.next=node
                tail_tmp=pre
                pre=next_node
            elif n%k==1:
                left_node=node
            node=next_node
        if n%k!=0 and tail_tmp:
            assert left_node
            tail_tmp.next=left_node
        if new_head:
            return new_head
        else:
            return left_node

    def reverse(self,first,end):
        assert first and end
        pre=None
        node=first
        while node!=end:
            tmp=node.next
            node.next=pre
            pre=node
            node=tmp
        end.next=pre

Meta

发布: 十二月 1, 2014

作者: Bone Lee 李智华

评论:  

字数统计: 222

下一篇: leetcode刷题 Jump Game II

上一篇: Top K problem

Bookmark and Share

Tags

code leetcode python

comments powered by Disqus

返回顶部