题目描述

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

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

示例 :
给定这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

• 你的算法只能使用常数的额外空间。

• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

题解

逆转单链表

参考：

• LeetCode 笔记系列六 Reverse Nodes in k-Group [学习如何逆转一个单链表]

• Non-recursive Java solution and idea

第一个逆转后就成了最后一个。然后遍历每个 node，把它放到链表的首位，最后一个就么成了第一个。
因为有放到链表首位的操作，所以还需要一个 dummy 头节点，下面是逆转单链表的代码：

/// <summary>
/// Reverse a link list between begin and end exclusively
/// Example, a linked list:
/// 0->1->2->3->4->5->6
/// |           |   
/// begin      end
/// 
/// after call begin = Reverse(begin, end)
///  
/// 0->3->2->1->4->5->6
///          |  |
///       begin end
/// </summary>
/// <param name="begin"></param>
/// <param name="end"></param>
/// <returns>The reversed list's 'begin' node, which is the precedence of node end</returns>
private static ListNode Reverse(ListNode begin, ListNode end)
{
    var curr = begin.next;
    var prev = begin;
    var first = curr;
    while (curr != end)
    {
        var next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    begin.next = prev;
    first.next = curr;
    return first;
}

主体方法：

public static ListNode ReverseKGroup(ListNode head, int k)
{
    if (head?.next == null || k == 1) return head;
    var dummy = new ListNode(0) {next = head};
    var begin = dummy;
    var i = 0;
    while (head!=null)
    {
        i++;
        if (i % k == 0)
        {
            begin = Reverse(begin, head.next);
            head = begin.next;
        }
        else
        {
            head = head.next;
        }
    }
    return dummy.next;
}