K个一组翻转链表(LeetCode--25.K个一组翻转链表)

题目描述

一个链表每 k 个节点一组进行翻转。k 是一个正整数，节点总数不足 k 保持原有顺序。

示例：
输入：1->2->3->4->5和k=3
输出：3->2->1->4->5

解析

实现技巧：递归实现

实现方法

1. 找到前k个结点（不足直接返回原链表）
2. 反转前k个结点产生反转链表，记为List1
3. 递归调用传入第k+1个以及之后的结点组成的新链表得到链表，记为List2
4. List2链接到List1之后即可

代码

private class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
public ListNode reverseKGroup(ListNode head, int k) {
    if(null == head){
        return head;
    }
    /*找到前k个结点*/
    ListNode tail = head;
    int i = 0;
    for(; i < k && tail != null; i++){
        tail = tail.next;
    }
    /*不足k个结点直接返回原链表*/
    if(i < k){
        return head;
    }
    /*反转前k个结点产生反转链表h*/
    ListNode h = reverseList(head, tail);
    /*递归调用传入第k+1个以及之后的结点组成的新链表得到链表，此链表链接到h之后*/
    head.next = reverseKGroup(tail, k);
    return h;
}
/*链表反转函数*/
private ListNode reverseList(ListNode head, ListNode tail){
    /*如果链表少于2个结点不需要反转*/
    if(head == null || head.next == null){
        return head;
    }
    /*定义三个引用，分别指向当前结点second，当前结点的前驱first，当前结点的后继third*/
    ListNode first = null;
    ListNode second = head;
    ListNode third = head;
    /*三引用依次后移，操作结点的next引用指向，直到当前结点second为tail停止*/
    while(second != tail){
        third = third.next;
        second.next = first;//当前结点next指向前驱
        first = second;
        second = third;
    }
    return first;
}

总结

代码目前在LeetCode上执行效率最高的解法，同时也是相对比较容易想到和实现的解法。主要在于熟练理解递归算法，了解它的解题思路，递归表达式，递归的结束条件等等，这样在实际解决问题中可以事半功倍。

LeetCode执行结果截图