LeetCode Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
Example:
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
Note:
- Only constant extra memory is allowed.
- You may not alter the values in the list's nodes, only nodes itself may be changed.
给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明 :
- 你的算法只能使用常数的额外空间。
- 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
题解:给定一个单链表和一个k,将单链表中每k个节点进行反转,然后将新生成的构成一个新的链表。
这里,是用一个stack来保存每k个节点,当节点个数为k个时,进行反转,利用stack栈的先进后出的特点即可。
public static ListNode reverseKGroup(ListNode head,int k)
{
if(head == null || k <= 1)
return head;
Stack<ListNode> stack = new Stack<>(); //用了一个栈来保存
ListNode dummy = new ListNode(-1); //新建了一个头节点,用来指向head节点
dummy.next = head;
ListNode pre = dummy; //两个节点
ListNode curr = head;
int num = 0;
while(curr != null) //当在前的那个指针一直往前走,并且每走一步,都需要使得节点个数加1,而且要看该节点个数值是否为k个
{
num += 1;
if(num % k == 0)
{
stack.push(curr); //如果是节点个数没有满足k,那么将这些节点全都放入stack栈中
curr = curr.next;
while(!stack.isEmpty()) //如果节点个数的和刚好为k,那么将保存在stack栈中的所有节点全部都取出来,然后重新构建单链表
{
pre.next = stack.pop();
pre = pre.next;
}
pre.next = curr; //这是每次k个节点反转之后,都将最后的那个指针指向下一个节点,防止断链
}
else if(num % k != 0)
{
stack.push(curr);
curr = curr.next;
}
}
return dummy.next;
}
注释写在代码中,可以供参考。此题一开始lz没啥思路,后来想到引入一个stack用来保存需要反转的节点,那么就豁然开朗,然后利用两个节点来进行反转。
推荐阅读
-
Leetcode解题 7. Reverse Integer 反转整数
-
LeetCode --- 783. Minimum Distance Between BST Nodes 解题分析
-
Leetcode 7. Reverse Integer
-
LeetCode:7. Reverse Integer
-
【leetcode】7. Reverse Integer
-
Leetcode 1530. Number of Good Leaf Nodes Pairs (python)
-
Leetcode 1519. Number of Nodes in the Sub-Tree With the Same Label (python)
-
LeetCode 1519. Number of Nodes in the Sub-Tree With the Same Label
-
[leetcode] 1315. Sum of Nodes with Even-Valued Grandparent
-
【Leetcode】190. Reverse Bits(二进制数反转)