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

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

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

双指针法

和区间翻转解法类似,只需先遍历链表确定长度,然后确定需要几次区间翻转即可。我们需要指针l 和tail分别记录区间翻转后左侧和右侧指针,进行翻转后的善后工作即可。其中,指针l每次赋值为待反转区间前一个指针,tail赋值为待翻转区间第一个指针,反转之后就是最后一个。

C++代码:

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int len = 0;
        ListNode *p = head;
        while (p) {
            len++;
            p = p->next;
        }
        p = head;
        ListNode *pre = NULL, *l, *tail, *t;
        for (int i = 0; i < len / k; i++) {
            l = pre;//初始化区间左右
            tail = p;
            pre = p;//初始化完要前移一下进入区间
            p = p->next;
            for (int j = 1; j <= k - 1; j++) {
                t = p->next;
                p->next = pre;
                pre = p;
                p = t;
            }
            if (i == 0) {head = pre;}//区间左边连接
            else {l->next = pre;}
            tail->next = p;//区间右边连接
            pre = tail;//为下一次翻转做准备,p本身已就位
        }
        return head;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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