LeetCode：Reverse Nodes in k-Group Java实现

LeetCode题目：Reverse Nodes in k-Group

题目概述

Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

解题方法

迭代

• 思路
  这道题跟之前的“反转链表”有些类似，不同之处是要先取出k个节点然后进行反转，同时要做好每段之间的连接。
  （1）分段的时候不仅取出k个节点，同时取出该段的前段的结束节点和后段的起始节点，用于连接；
  该段反转前：
  
  该段反转后：
  
  （2）K个节点反转的过程：
  采用头插法：每回将 cur 节点插到该段的最前面
  
• 代码

// 反转一段链表  pre-上一段的结束节点  next-下一段的起始节点
public ListNode reverse(ListNode pre, ListNode next){
	ListNode last = pre.next;
	ListNode cur = last.next;
	while(cur != next){
		last.next = cur.next;
		cur.next = pre.next;
		pre.next = cur;
		cur = last.next;
	}
	return last;
}
    
    
public ListNode reverseKGroup(ListNode head, int k) {
	if(head == null || k == 1){
		return head;
	}
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	ListNode pre = dummy;
	ListNode cur = head;
	
	int count = 0;
	while(cur != null){
		count ++;
		ListNode next = cur.next;
		if(count == k){
			pre = reverse(pre, next);
			count = 0;
		}
		cur = next;
	}
	return dummy.next;
}

递归

• 思路
  （1）入参head为该段的起始节点，K为反转段的个数；
  （2）取出该段（从head开始）第K+1节点；
  
  （3）递归传入K+1节点和k，作为下一段继续开始反转，需要返回的数据为下一段反转之后的起始节点；
  （4）反转这一段K个节点：取出head节点，连接到cur（K+1节点：下一段的起始节点）节点之前，向后移动head节点，向前移动cur节点；

  • a
    
  • b
    
  • c
    
  • d
    

• e
  

• 代码

public ListNode reverseKGroup(ListNode head, int k) {
	if(head == null || k == 1){
		return head;
	}
	ListNode cur = head;
	int count = 0;
	while(cur != null && count != k){
		cur = cur.next;
		count ++;
	}
	if(count == k){
		cur = reverseKGroup(cur, k);
		while(count-- > 0){
			ListNode next = head.next;
			head.next = cur;
			cur = head;
			head = next;
		}
		head = cur;
	}
	return head;
}