首页 > 其他 > 详细

LeetCode-Reverse Nodes in k-Group

时间:2014-10-27 10:47:58      阅读:253      评论:0      收藏:0      [点我收藏+]

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

 

思路:一开始是想要动态规划的方式,即写一个反转函数,每K个字符调用一次,但是较大的问题就是要记录反转后链表的首尾指针。后来查到可以直接原地反转的方式,如下图bubuko.com,布布扣

 

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        int cnt = 0;
        bool isHead = true;  //是否链头
        ListNode *p = head, *q = NULL, *prev = NULL;
        while(p){
            cnt = 0;
            q = p->next;
            while(q && cnt < k-2){
                q = q->next;
                cnt++;
            }
            if(q == NULL){       //不够K个数
                return head;
            }
            cnt = 0;
            while( cnt < k-1){
                q = p->next;
                p->next = q->next;
                if(isHead){
                    q->next = head;
                    head = q;
                }else{
                    q->next = prev->next;
                    prev->next = q;
                }
                cnt++;
            }
            isHead = false;
            prev = p;
            p = p->next;
        }
        return head;
    }
};

 

LeetCode-Reverse Nodes in k-Group

原文:http://www.cnblogs.com/crazelee/p/4053597.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!