LeetCode——K个一组翻转链表

NO.25 K个一组翻转链表 困难

思路一：迭代实现 和徒手挖地球九周目中NO.24两两交换链表中的节点的迭代法思路一样，不过NO.24题中的k是2而已。

1. 哑节点dummy。pre指向待翻转子链表的前驱，end指向待翻转子链表的尾节点。然后，start指向待翻转子链表的头节点，next指向待翻转子链表的后继。最后断开待翻转子链表和剩余链表，翻转第一组。
2. 反转完成之后，将start节点和next节点连接。移动pre指向start节点，end指向pre节点，检查end.next不为空，所以向后移动end到下一组待翻转子链表的尾节点，start指向待翻转子链表的头节点，next指向待翻转子链表的后继。翻转第二组。
3. 第二组翻转完成，将start节点和next节点连接。移动pre指向start节点，end指向pre节点，检查end.next不为空，所以向后移动end，但是剩余节点不足k个。所以翻转全部，返回dummy.next。

这里还有一个问题就是如何翻转子链表reverse(head)？用上述第一组子链表为例：

curr指向当前节点，pre指向curr之前节点，next指向curr之后节点，翻转过程比较简单，直接看图。

public ListNode reverseKGroup(ListNode head, int k) {
    if (k==1)return head;
    //初始化哑节点、pre、end
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    ListNode pre=dummy,end=dummy;
    while (end.next!=null){
        //移动end指向待翻转子链表的尾部,如果剩余节点不足k个，则翻转完成返回head
        for (int i = 0; i < k&& end!=null; i++) end=end.next;
        if (end==null)break;
        //start指向待翻转子链表头节点，next指向未翻转部分的头节点
        ListNode start=pre.next,next=end.next;
        end.next=null;
        pre.next=reverse(start);
        //连接完成翻转部分和未翻转部分
        start.next=next;
        //移动pre和end
        pre=start;
        end=pre;
    }
    return dummy.next;
}
//翻转子链表
private ListNode reverse(ListNode head) {
    ListNode pre=null,curr=head;
    while (curr!=null){
        ListNode next=curr.next;
        curr.next=pre;
        pre=curr;
        curr=next;
    }
    return pre;
}

时间复杂度：O(nk) n是节点总数。

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github