题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

采用快慢指针,快指针与慢指针相距k个节点,每次分组后采用头插法让快指针到慢指针的节点翻转。如果最后不够k个节点,则直接拼接链表。注意每次分组后需要用新链表的尾节点去链表剩下没有遍历的节点以保证链表不会断。这里没有去记录尾节点,而是通过头节点去遍历得到尾节点,应该可以优化直接记录下尾节点。

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        ListNode* new_head=NULL;
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* group_head = NULL;
        while(fast)
        {
            group_head = NULL;
            //快指针先移动k个位置去占位;
            int group = k;
            while(group>0)
            {
                if(fast == NULL)
                    break;
                fast = fast->next;
                group--;
            }

            if(group==0)
            {
                //够k个位置;
                ListNode* tmp = NULL;
                while(slow && slow!=fast)
                {
                    tmp = slow->next;
                    //采用头插法;
                    if(group_head == NULL)
                    {
                        group_head = slow;
                        slow->next = NULL;
                    }else{
                        slow->next = group_head;
                        group_head = slow;
                    }
                    slow = tmp;
                }

                if(!new_head)
                {
                    new_head = group_head;
                }else
                {
                    ListNode* p = new_head;
                    while(p->next) p = p->next;
                    p->next = group_head;
                }
            }else
            {
                if(!new_head)
                {
                    new_head = slow;
                }else
                {
                    ListNode* p = new_head;
                    while(p->next) p = p->next;
                    p->next = slow;
                }
                break;
            }
        }
        return new_head;
    }
};
全部评论

相关推荐

练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
嵐jlu:我是山川🐔里🐔🧱的,阿里系简历全过; 你这简历一看就还是半成品啊,没有荣誉经历奖项什么的吗?
投递阿里巴巴集团等公司10个岗位
点赞 评论 收藏
分享
06-11 17:39
门头沟学院 Java
小呆呆的大鼻涕:卧槽,用户彻底怒了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:22
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务