25 Reverse Nodes in k-group

编写链表反转的辅助函数，同时使用dummy作为哑头结点，使用prehead，cur_head来保存前一个部分的反转链表以及当前反转链表。

Python

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        prev, curr = None, head
        while curr:
            nexttemp = curr.next
            curr.next = prev
            prev = curr
            curr = nexttemp
        return prev

    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        cur = head
        prev_head = dummy
        cur_head = head
        i = 0
        while cur:
            i += 1
            if i == k:
                temp = cur.next
                cur.next = None
                prev_head.next = self.reverseList(cur_head)
                prev_head = cur_head
                i = 0
                cur = temp
                cur_head = temp
            else:
                cur = cur.next
        if cur_head:
            prev_head.next = cur_head
        return dummy.next ### 返回哑链表头结点的next指针，这样可以方便处理头结点为空的情况

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        while(curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = head;
        ListNode prev_head = dummy;
        ListNode cur_head = head;
        int i = 0;
        while (cur != null){
            i += 1;
            if (i == k){
                ListNode temp = cur.next;
                cur.next = null;
                prev_head.next = this.reverseList(cur_head);
                //go on
                prev_head = cur_head;
                i = 0;
                cur = temp;
                cur_head = temp;
            }
            else{
                cur = cur.next;
            }
        }
        if(cur_head != null){
            prev_head.next = cur_head;
        }
        return dummy.next;    
    }
}