分组并翻转链表

2019-09-02

题目

给定一个单链表的头节点 head,实现一个调整单链表的函数，使得每K个节点之间为一组进行逆序，并且从链表的尾部开始组起，头部剩余节点数量不够一组的不需要逆序。（不能使用队列或者栈作为辅助）

例如：

链表:1->2->3->4->5->6->7->8->null, K = 3。
那么 6->7->8，3->4->5，1->2各为一组。
调整后：1->2->5->4->3->8->7->6->null。
其中 1，2不调整，因为不够一组。

解法

首先，这里先分为几个子部分进行分析：

1. 翻转链表

整体使用递归的思想。

若size为1时，翻转不发生，返回自身。

若size为2时，翻转的方式为：tail->next = head; head->next = nil; 然后返回tail。

若size大于2，则将head后面的子链表继续递归，之后与head进行操作：result->next = head; head->next = nil; 最后返回result。

/** 翻转链表 */
LinkNode *reverseLinkList(LinkNode *linkList) {
    // 只有自身一个
    if (!linkList.data || !linkList.next) {
        // 直接返回自身
        return linkList;
    }
    
    // 超过一个的，子链表递归翻转
    LinkNode *result = reverseLinkList(linkList.next);
    
    // 头结点的next这时已经指向的是，翻转后result链表的尾部节点，
    // 让尾部节点的next指向原头节点
    linkList.next.next = linkList;
    // 原头节点作为尾部节点
    linkList.next = nil;
    
    // 返回反转后的头节点
    return result;
}

2. 链表分组。

还是使用递归的思想。

从头遍历链表，取出指定索引为k的子链表。

若子链表个数不够，根据题目要求，不翻转，直接返回。

若子链表符合要求，将此子表与其他部分分割为两个链表。

将子表翻转并返回；其他部分则继续进行递归操作。

最后，合并两部分，则得到最终结果链表。

/** 分组并翻转链表 */
LinkNode *groupAndReverseLinkList(LinkNode *linkList, NSInteger groupSize) {
    // 声明头指针
    LinkNode *head = linkList;
    
    // 取出一组
    for (NSInteger index = 1; index < groupSize && head; index += 1) {
        head = head.next;
    }
    
    if (!head) {
        // 不足一组（不足groupSize时，当前node已经为空）
        // 不做反转，直接返回
        return linkList;
    }
    
    // 够一组，将此组与后面链表分隔
    
    // 后面的子表
    LinkNode *tail = head.next;
    
    // 原满足的组作为单独组
    head.next = nil;
    // 将满足的组进行反转
    LinkNode *resultHead = reverseLinkList(linkList);
    
    // 子表继续递归操作
    LinkNode *result = groupAndReverseLinkList(tail, groupSize);
    
    
    // 连接两部分（反转后的满足组，尾部节点为原头节点）
    linkList.next = result;
    
    return resultHead;
}

3. 从前向后 -> 从后向前

由于单链表访问的局限性，我们只能从头向后访问，因此，此题目我们转化为从前向后的分组翻转（两次翻转，负负得正）：

整体链表翻转。
从前向后进行分组操作。
将结果链表再次整体翻转，得到最终结果。

// head为头结点，没有实际意义
// 翻转链表
head.next = reverseLinkList(head.next);
// 从前向后进行分组翻转，3个为一组
LinkNode *result = groupAndReverseLinkList(head.next, 3);
// 翻转链表（得到从后向前的分组结果）
head.next = reverseLinkList(result);

代码地址：GroupAndReverse

参考链接：
一道字节跳动的算法面试题，你能做出来吗？