链表中的节点每k个一组翻转

public class Solution {
    public static ListNode reverseKGroup(ListNode head, int k) {
		if(head == null || head.next == null || k < 2) return head;
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		ListNode pre = dummy, cur = head, temp;
		int len = 0;
		while (head != null) {
			len ++ ;
			head = head.next;
		}
		for (int i = 0; i < len / k; i ++ ) {
			for (int j = 1; j < k; j ++ ) {
				temp = cur.next;
				cur.next = temp.next;
				temp.next = pre.next;
				pre.next = temp;
			}
			pre = cur;
			cur = cur.next;
		}
		return dummy.next;
	}
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode end = head;
        for (int i = 0; i < k; i++) {//找到翻转部分尾节点的下一个节点
            if (end == null) {
                return head;
            }
            end = end.next;
        }
        ListNode pre = null, cur = head;
        while(cur != end) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        head.next = reverseKGroup(end, k);//尾节点指向下一个翻转的头节点
        return pre;
    }
}

class Solution {
public:
    /// 参考翻转pairs，翻转x~x+(k-1）之间的节点， x->next = reverseKGroup(x+k,k)
    ListNode* reverse(ListNode *first,ListNode *last)
    {
        ListNode *pre = nullptr;
        while(first!=last)
        {
            ListNode *temp = first->next;
            first->next = pre;
            pre = first;
            first = temp;
        }
        return pre;
    }
    ListNode *reverseKGroup(ListNode *head, int k) 
    {
        if(!head)
            return nullptr;
        ListNode *node = head;
        for(int i=0;i<k;i++)
        {
            if(!node)
                return head;
            node = node->next;
        }
        ListNode *newHead = reverse(head,node);
        head->next = reverseKGroup(node,k);
        return newHead;
    }
};

class Solution:
    def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
        #递归
        cur = head
        count = 0
        while cur and count!= k:
            cur = cur.next
            count += 1
        if count == k:
            cur = self.reverseKGroup(cur, k)
            while count:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                count -= 1
            head = cur   
        return head

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode prev = null,curr = head;
        int times = k;
        while (times-- > 0){
            if(curr == null){
                return restore(prev);
            }

            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        head.next = reverseKGroup(curr, k);
        return prev;
    }

    private ListNode restore(ListNode head){    //不足k个时再反转还原
        ListNode prev = null,curr = head;
        while (curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Solution {
public:
    ListNode* reverse(ListNode* node, int size, int k) {
        if (!node) return nullptr;
        if (size < k) return node;
        ListNode* end = node;
        ListNode* prev = node;
        ListNode* p = node->next;
        ListNode* next = nullptr;
        for (int i = 1; i < k; i++) {
            next = p->next;
            p->next = prev;
            prev = p;
            p = next;
        }
        end->next = reverse(next, size - k, k);
        return prev;
    }
    
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (k == 1) return head;
        int size = 0;
        ListNode* p = head;
        while (p != nullptr) {
            size++;
            p = p->next;
        }
        return reverse(head, size, k);
    }
};

//明显递归解决，翻转第一组之后，以第二组的开头为头节点，继续翻转，知道转翻到最后，返回。
public ListNode reverseKGroup(ListNode head, int k) {
       		 	   if(head==null||head.next==null)
			    	   return head;
			     	ListNode h=new ListNode(0);
			     	h.next=head;
			       	ListNode next=null,tmp=head,cur=head;
			       	for(int i=1;i<k;i++){
	                    cur=cur.next;
	                    if(cur==null)
	                        return head;
	                }
			       	next=cur.next;
			       	while(head.next!=next){
			       		tmp=head.next;
			       		head.next=tmp.next;
			       		tmp.next=h.next;
			       		h.next=tmp;
			       	}
			       	head.next=reverseKGroup(next,k);
			       	return h.next;
    }

public ListNode reverseKGroup (ListNode head, int k) {
        ListNode tail=head;//tail为分组界限
        for(int i=0;i<k;i++){   //如果不足k个
            if(tail==null) return head;
            tail=tail.next;
        }
        //如果足k个,反转链表
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=tail){//因为下一段的头是tail
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        head.next=reverseKGroup(tail,k);
        return pre;
    }

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 时间复杂度O(N)，空间复杂度O(1)
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head, *tmp;
        while (true) {
            // 判断能否反转
            tmp = cur;
            for (int i = 0; i < k; ++i) {
                if (tmp) tmp = tmp->next;
                else return dummy->next;  // 节点已到空，不能反转，直接返回头节点
            }
            // 开始反转
            for (int i = 1; i < k; ++i) {
                tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = pre->next;
                pre->next = tmp;
            }
            pre = cur;
            cur = cur->next;
        }
        return nullptr;
    }
};

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res,cur = head;
        int length = 0;
        //获取链表的长度
        while (head != null) {
            length ++;
            head = head.next;
        }
        //需要分多少组
        int count = length / k;
        //需要翻转多少个链表
        while (count > 0) {
            //反转链表
            for (int j = 1; j < k; j++) {
                ListNode temp = cur.next;
                cur.next = temp.next;
                temp.next = pre.next;
                pre.next = temp;
            }
            count --;
            //翻转链表，当count已经为0，没必要再找一下节点，防止找下一个节点越界
            if (count > 0) {
                //cur节点刚好是链表翻转后的最后一个节点
                pre = cur;
                //cur.next是下一个需要翻转的起始节点
                cur = cur.next;
            }
        }
        return res.next;
    }

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseKGroup( head ,  k ) {
    // write code here
    let headNode = head
    //当k超过节点数时，直接返回
    for(let i=0;i<k;i++){
        if(headNode == null){
            return head
        }
        headNode = headNode.next
    }
    
    //对k个节点进行逆转（进行k-1此指向转换）
    let cur = head.next
    let pre = head
    for(let i=1;i<k;i++){
        let tmp = cur.next
        cur.next = pre
        pre = cur 
        cur = tmp       
    }
    //递归对下一组k个进行逆转，且每次都是把head指向下一组
    head.next = reverseKGroup(cur,k)
    //返回每一组逆序后实际的头节点（就是当前pre指向的，即每组第k个元素）
    return pre
}
module.exports = {
    reverseKGroup : reverseKGroup
};

import java.util.*;

public class Main {
    static class ListNode{
        int val;
        ListNode next;
        ListNode(int val){
            this.val = val;
        }
    }
        // 这里全是输入处理
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.nextLine();
            int k = in.nextInt();
            ListNode head = new ListNode(-1);
            ListNode p = head;
            String[] strArray = str.split(" ");
            for(int i = 0; i < strArray.length - 1; i++){
                p.next = new ListNode(Integer.parseInt(strArray[i]));
                p = p.next;
            }
            head = reverseK(head.next, k);
            printList(head);
        }
    }
        // 输出处理
    private static void printList(ListNode head) {
        while(head != null){
            System.out.print(head.val);
            if(head.next != null){
                System.out.print("->");
            }
            head = head.next;
        }
    }
        // 核心程序
    private static ListNode reverseK(ListNode head, int k) {
        if(k == 1 || head == null || head.next == null){
            return head;
        }
        ListNode a = head, b = head;
        for(int i = 0; i < k; i++){
            if(b == null){
                return head;
            }
            b = b.next;
        }
        ListNode newHead = reverse(a, b);
        head.next = reverseK(b, k);
        return newHead;
    }

    private static ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null, cur = a;
        while(cur != b){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return  pre;
    }
}

}

struct ListNode* reverseKGroup(struct ListNode* head, int k ) {
    // write code here
    struct ListNode *tail = head;
    //1、递归结束的点(k个为一组，不足k个直接返回head)
    for (int i = 0; i < k; i++){
        if (tail == NULL) {
            return head;
        }
        tail = tail->next;
    }

    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *nex;
    //2、每一级的任务
    while (cur != tail) {
        nex = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    head->next = reverseKGroup(tail, k);
    //3、找到返回值
    return pre;
}

def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
    # write code here
    le = 0
    # 虚拟头结点
    hv = ListNode(0)
    hv.next = head
    t = hv
    # 计算长度
    while t.next is not None:
        le += 1
        t = t.next
    rev_time = le // k # 共需翻转rev_time次
    pre = hv
    cur = hv.next
    p,c = pre,cur # 暂存pre和cur
    for _ in range(rev_time):# 共需翻转rev_time次
        for _ in range(k):# 每次翻转k个元素
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        # 连接头尾结点并更新p和c
        p.next = pre
        p = c
        c.next = cur
        c = cur
    return hv.next

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    //翻转 a--b之间
    ListNode* reverselistnode(ListNode*a,ListNode*b){
        ListNode *pre= nullptr;
        while(a!=b){
            ListNode *temp =a->next;
            a->next =pre;
            pre =a;
            a =temp;
        }
        return pre;
    }
    
    
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head ==nullptr){
            return nullptr;
        }
        ListNode *a =head;
        ListNode *b =head;
        //a原地不动 b走k个  形成a---b区间
        for(int i=0;i<k;i++){
            if(b!=nullptr){
                b=b->next;
            }else{
                return head;
            }
        }
        
        //翻转ab区间 更新新的区间b--k
        ListNode *newhead =reverselistnode(a,b);
        a->next =reverseKGroup(b,k);
        return newhead;
        
        
    }
};

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        //统计链表个数
        int n = 0;
        ListNode p = head;
        while (p != null) {
            n++;
            p = p.next;
        }
        //计算反转次数
        int t = n / k;
        if (t == 0)
            return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //记录上一次的尾节点
        ListNode lastTail = dummy;
        p = head;
        while (t-- > 0) {
            //记录本次反转的尾结点
            ListNode curTail = p;
            ListNode pre = null;
            for (int i = 0; i < k; i++) {
                ListNode next = p.next;
                p.next = pre;
                pre = p;
                p = next;
            }
            //完成后pre为反转后的头结点
            lastTail.next = pre;
            lastTail = curTail;
        }
        //处理最后一部分
        lastTail.next = p;
        return dummy.next;
    }

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(head==null) return null;
        ListNode a,b;
        a=b=head;
        for(int i=0;i<k;i++){
            if(b==null) return head;
            b=b.next;
        }
        ListNode newHead=reverse(a,b);
        a.next=reverseKGroup(b,k);
        return newHead;
    }
    public ListNode reverse(ListNode a,ListNode b){
        ListNode pre,cur,nxt;
        pre=null;cur=a;nxt=a;
        while(cur!=b){
            nxt=cur.next;
            cur.next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
}