每周一道算法题(二十一)

本周题目难度级别"hard"

题目:给你一个单向链表和一个数字k，要求将链表的每k个节点进行倒置，如链表为［1,2,3,4,5,6,7,8,9,10］，k为4,则返回的链表为［4,3,2,1,8,7,6,5,9,10］

思路：这个实现的方式有很多，主要是递归及其递归的优化，我用的方法很low，也比较容易理解，我就少写点注释了，下周有时间再优化吧，下面是代码：

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (head == NULL || k <= 1) return head;
    if (head->next == NULL) return head;
    struct ListNode* newHead = head;
    int i,j;
    i = k - 1;
    //找到新的头节点
    while (i != 0) {
        if (newHead->next == NULL) return head;
        newHead = newHead->next;
        i--;
    }
    struct ListNode* result = newHead;
    struct ListNode* temp1 = head;
    //记录下次遍历的起始节点
    struct ListNode* mark = newHead->next;
    //将第一个k节点进行倒置
    for (i = k-2; i >= 0; i--) {
        j = i;
        while (j != 0) {
            temp1 = temp1->next;
            j--;
        }
        result->next = temp1;
        result = result->next;
        result->next = NULL;
        temp1 = head;
    } 
    result->next = mark;
    temp1 = mark;
    struct ListNode* temp2 = temp1;
    //完成剩下的链表每k个节点进行倒置
    while (mark != NULL) {
        for (i = k-1; i >= 0; i--) {
            j = i;
            temp2 = temp1;
            while (j != 0) {
                if (temp2->next == NULL) return newHead;
                temp2 = temp2->next;
                j--;
            }
            //第一轮遍历的时候记录下一个需要倒置的起始节点
            if (i == k-1) mark = temp2->next;
            result->next = temp2;
            result = result->next;
            result->next = NULL;
        }
        result->next = mark;
        temp1 = mark;
    }
    return newHead;
}

小插曲

一开始我把题目理解错了，所以就加送一个吧，下面这道题的题目是：给你一个单向链表和数字k，要求每k个节点交换，即第一个节点和第k个节点交换，第k＋1个节点和第2k个节点交换。。。我也简单写下注释：

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (head == NULL || k <= 1) return head;
    if (head->next == NULL) return head;
    struct ListNode* newHead = head;
    int n = k - 1;
    //找到新的头节点
    while (n != 0) {
        if (newHead->next == NULL) return head;
        newHead = newHead->next;
        n--;
    }
    struct ListNode* result = newHead;
    struct ListNode* temp = newHead->next;
    result->next = head->next;
    n = k - 2;
    while (n != 0) {
        result = result->next;
        n--;
    }
    result->next = head;
    result = result->next;
    //头节点和第k个节点交换完成
    result->next = temp;
    //遍历交换剩下的节点
    while(result->next != NULL) {
        struct ListNode* temp1 = result->next;
        temp = result->next; 
        n = k - 1;
        //找到第2k个节点
        while (n != 0) {
            if (temp->next == NULL) return newHead;
            temp = temp->next;
            n--;
        }
        struct ListNode* temp2 = temp->next;
        temp->next = temp1->next;
        result->next = temp;
        result = result->next;
        n = k - 2;
        while (n != 0) {
            result = result->next;
            n--;
        }
        //交换完成
        result->next = temp1;
        result = result->next;
        result->next = temp2;
    }
    return newHead;
}

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!