25. k个一组翻转链表

题目描述：

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

---

代码实例：

 public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    /**
     * @Description:
     * @auther: DaleyZou
     * @date: 13:46 2018-8-8 
     * @param: head 链表的头结点
     * @param: k k 个节点一组进行翻转
     * @return: ListNode
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode currentNode = head;
        if (currentNode == null || k < 0){
            return head;
        }
        int count = 0;
        while (currentNode != null && count < k){ // find the k+1 node
            currentNode = currentNode.next;
            count++;
        }
        if (count == k){ // if k+1 node is found
            currentNode = reverseKGroup(currentNode, k); // reverse list with k+1 node as head
            while (count-- > 0){ // reverse current k-group:
                ListNode temp = head.next;
                head.next = currentNode;
                currentNode = head;
                head = temp;
            }
            head = currentNode;
        }
        return head;
    }

理解：

上述代码用到了递归，以 k 个节点为一组来实现递归的翻转。对于使用递归，重要的就是理解递归中的一次过程。

---

下面我们就来看一下上述代码中，一次递归都干了些什么。

下面代码的作用：

我们有一个链表 1-> 2 -> 3 -> 4 -> 5 ,我们将实现链表前四个节点的翻转， 也就是要得到的结果为： 4 -> 3 -> 2 -> 1 -> 5

代码如下：

public ListNode reverse(ListNode head, int k){
        int count = 0;
        ListNode currentNode = head;
        while (currentNode != null && count < k){
            currentNode = currentNode.next;
            count++;
        }
        while (count-- > 0) {
            ListNode tmp = head.next;
            head.next = currentNode;
            currentNode = head;
            head = tmp;
            ListNode out = currentNode;
            while (out != null){
                System.out.print(out.val + " ");
                out = out.next;
            }
            System.out.println();
        }
        return currentNode;
    }
    public static void main(String[] args){
        LeetCode25 leetcode25 = new LeetCode25();
        
        // 初始化5个链表节点
        ListNode head = new ListNode(1);
        ListNode head1 = new ListNode(2);
        ListNode head2 = new ListNode(3);
        ListNode head3 = new ListNode(4);
        ListNode head4 = new ListNode(5);

        // 添加节点间的关联关系
        head.next = head1;
        head1.next = head2;
        head2.next = head3;
        head3.next = head4;

        // 对前四个节点进行翻转
        ListNode reverse = leetcode25.reverse(head, 4);
    }

代码输出结果如下：

>1 5

2 1 5

3 2 1 5

4 3 2 1 5

画一个图理解一下：

---

我们实现了一个 k 组翻转，那么实现整个链表的 k 组翻转就是加上递归啦！