leetcode K 个一组翻转链表

代码如下:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *l1=head;
        int n=0;
        while(l1!=NULL)//获取链表长度
        {
            l1=l1->next;
            n++;
        }
        if(n<k || k==1)//链表长度小于k,或者k=1,这两种情况不用翻转
        {
            return head;
        }
        int a=n%k;//得到链表末不用翻转的位置
        ListNode *l_end=NULL;//上一个k个节点的尾节点
        l1=head;
        ListNode *l_head=head->next;//下一个k节点的头节点
        ListNode *l_end0=head;//当前k个节点的尾节点
        ListNode *newhead=NULL;//将当前k个节点单独看成一个链表,此时的头结点
        ListNode *node1=NULL;//用作链表翻转的辅助节点
        int c=k-1;
        while(c--)
        {
            head=head->next;//将头节点指针指向翻转之后的头结点,也就是第一批k节点翻转之后的头节点
        }
        for(int i=1;i<n-a;i=i+k)
        {
            int pos=k-1;
            while(pos--)
            {
            	//下一个k节点的头节点
                l_head=l_head->next;//定位到相应节点处
                //当前k个节点的尾节点
                l_end0=l_end0->next;//定位到相应节点处
            }
            newhead=l1;//得到当前k个节点的头节点
            node1=newhead->next;
            l_end0->next=NULL;//当前尾节点的next定义为空,使当前k个节点变成一个独立的链表进行翻转
            //进行翻转
            while(node1!=NULL)
            {
                ListNode *node_1=node1->next;
                node1->next=newhead;
                newhead=node1;
                node1=node_1;
            }

			//判断上一个k个节点的尾节点是否为空,不为空就指向当前k个节点翻转之后的头节点
            if(l_end!=NULL)
            {
                l_end->next=newhead;
            }

            l1->next=l_head;//将当前k节点的尾节点指向下个的头
            l_end=l1;//更新翻转之后k节点的尾节点,作为下次翻转的前k个的尾节点
            l1=l_head;//当前位置利于在下次循环更新下下次k个节点的头节点
            l_end0=l1;//当前位置利于在下次循环更新下次k个节点的尾节点
            if(l1!=NULL)
            {
                l_head=l1->next;//如果为空,就不进行更新,说明到最后了
            }
        }
            return head;
    }
};
上一篇:IE7下元素的 'padding-top' 遇到 'clear' 特性在某些情况下复制到 'padding-bottom'


下一篇:2016年十大*开源项目