「力扣」第 25 题:K 个一组翻转链表(困难)
- 英文网址:25. Reverse Nodes in k-Group ;
- 中文网址:25. k个一组翻转链表 。
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5 当 k = 2 时,应当返回: 2->1->4->3->5 当 k = 3 时,应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
Java 代码:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 使用递归写法的话,先考虑特殊情况
if (head == null || head.next == null || k <= 1) {
return head;
}
// 探测长度的结点
ListNode tempNode = head;
int curK = k;
while (tempNode != null && curK != 0) {
curK--;
tempNode = tempNode.next;
}
if (curK == 0) {
// 下面开始反转
ListNode pre = null;
ListNode curNode = head;
for (int i = 0; i < k; i++) {
ListNode nextNode = curNode.next;
curNode.next = pre;
pre = curNode;
curNode = nextNode;
}
head.next = reverseKGroup(tempNode, k);
return pre;
}
return head;
}
}
Java 代码:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
public ListNode(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("arr can not be empty");
}
this.val = nums[0];
ListNode curr = this;
for (int i = 1; i < nums.length; i++) {
curr.next = new ListNode(nums[i]);
curr = curr.next;
}
}
@Override
public String toString() {
StringBuilder s = new StringBuilder();
ListNode cur = this;
while (cur != null) {
s.append(cur.val + " -> ");
cur = cur.next;
}
s.append("NULL");
return s.toString();
}
}
// 参考资料:https://blog.csdn.net/weiyongle1996/article/details/78473055
public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 使用递归写法的话,先考虑特殊情况
if (head == null || head.next == null || k <= 1) {
return head;
}
// 探测长度的结点
ListNode tempNode = head;
int curK = k;
while (tempNode != null && curK != 0) {
curK--;
tempNode = tempNode.next;
}
// 如果够数了,先考虑反转
if (curK == 0) {
// 下面开始反转
ListNode pre = null;
ListNode curNode = head;
for (int i = 0; i < k; i++) {
ListNode nextNode = curNode.next;
curNode.next = pre;
pre = curNode;
curNode = nextNode;
}
head.next = reverseKGroup(tempNode, k);
return pre;
}
return head;
}
public static void main(String[] args) {
int[] nums = new int[]{1, 2};
ListNode head = new ListNode(nums);
Solution solution = new Solution();
ListNode reverseKGroup = solution.reverseKGroup(head, 2);
System.out.println(reverseKGroup);
}
}