0025-k个一组翻转链表

k个一组翻转链表

方案一

际上是把原链表分成若干小段，然后分别对其进行翻转，那么肯定总共需要两个函数，一个是用来分段的，一个是用来翻转的，我们就以题目中给的例子来看，对于给定链表1->2->3->4->5，一般在处理链表问题时，我们大多时候都会在开头再加一个dummy node，因为翻转链表时头结点可能会变化，为了记录当前最新的头结点的位置而引入的dummy node，那么我们加入dummy node后的链表变为-1->1->2->3->4->5，如果k为3的话，我们的目标是将1,2,3翻转一下，那么我们需要一些指针，pre和next分别指向要翻转的链表的前后的位置，然后翻转后pre的位置更新到如下新的位置,以此类推，只要next走过k个节点，就可以调用翻转函数来进行局部翻转了

借助单链表实现

C-源代码

struct ListNode *reverseList(struct ListNode *head) {
    
    struct ListNode *cur = head;
    struct ListNode *prev = NULL;
    while(cur) {
        
        struct ListNode *temp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = temp;
    }
    
    return prev;
}

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    
    struct ListNode *root = NULL;
    struct ListNode *p = NULL;
    
    while(head != NULL) {
        
        struct ListNode *tempHead = head;
        struct ListNode *tempP = NULL;
        
        int count = 0;
        bool isReverse = true;
        
        while(count < k) {
            
            if (head == NULL) {
                
                isReverse = false;
                break;
            }
            tempP = head;
            head = head->next;
            count++;
        }
        tempP->next = NULL;
        
        if (isReverse) {
            
            if (root == NULL) {
                
                root = reverseList(tempHead);
                p = tempHead;
            }
            else {
                
                p->next = reverseList(tempHead);
                p = tempHead;
            }
        }
        else {
            
            if (root == NULL) {
                
                root = tempHead;
            }
            else {
                
                p->next = tempHead;
            }
        }
    }
    
    return root;
}

/**
 k个一组翻转链表测试
 */
void test_0025(void)
{
    int arr[5] = { 1, 2, 3, 4, 5 };
    struct ListNode *head = linkListCreateHead(arr, sizeof(arr) / sizeof(arr[0]));
    

    printf("========k个一组翻转链表测试========\n");
    printNode(head);
    struct ListNode *new = reverseKGroup(head->next, 2);
    printNode(new);
}

参考Grandyang