一、题目
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例 :
给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
二、解答
2.1方法一:k个一组翻转
步骤分解:
- 链表分区为已翻转部分+待翻转部分+未翻转部分
- 每次翻转前,要确定翻转链表的范围,这个必须通过 k 此循环来确定
- 需记录翻转链表前驱和后继,方便翻转完成后把已翻转部分和未翻转部分连接起来
- 初始需要两个变量 pre 和 end,pre 代表待翻转链表的前驱,end 代表待翻转链表的末尾
- 经过k此循环,end 到达末尾,记录待翻转链表的后继 next = end.next
- 翻转链表,然后将三部分链表连接起来,然后重置 pre 和 end 指针,然后进入下一次循环
- 特殊情况,当翻转部分长度不足 k 时,在定位 end 完成后,end==null,已经到达末尾,说明题目已完成,直接返回即可
- 时间复杂度为 O(n*K) 最好的情况为 O(n) 最差的情况未 O(n^2)
- 空间复杂度为 O(1)除了几个必须的节点指针外,我们并没有占用其他空间
2.1.1 代码版本一
public ListNode reverseKGroup(ListNode head, int k) {
ListNode node = new ListNode(0);
node.next = head;
ListNode pre = node;
ListNode end = node;
while (end.next != null) {
for (int i = 0; i < k && end != null; i++) end = end.next;
if (end == null) break;
ListNode start = pre.next;
ListNode next = end.next;
end.next = null;
pre.next = reverse(start);
start.next = next;
pre = start;
end = pre;
}
return node.next;
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
2.1.2 代码版本二
public ListNode reverseKGroup(ListNode head, int k) {
int len = 0;
ListNode temp = head;
//获取链表长度
while (temp != null){
len++ ;
temp = temp.next;
}
//需要反转的组数
int cnt = len / k;
if(cnt <= 0 || k == 1){
return head;
}
ListNode node = new ListNode(0);
//当前节点head的前节点
ListNode pre = node;
//当前节点head的后节点
ListNode next = null;
//当前组反转后的尾节点
ListNode tail = null;
int i = 1;
while (head != null && cnt > 0){
if (i <= k){
next = head.next;
head.next = pre.next;
pre.next = head;
//当前组反转后的尾节点即反转前的首节点
if (i == 1){
tail = head;
}
//当前组反转完成,pre指向尾节点
if (i == k){
pre = tail;
i = 0;
cnt--;
}
head = next;
}
i++;
}
//存在未反转的节点
if (next != null){
pre.next = head;
}
return node.next;
}
2.2方法二:栈+递归
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null){
return null;
}
if (k==0||k==1){
return head;
}
Stack<ListNode> stack = new Stack<ListNode>();
boolean flag = false;
for (int i=0; i<k; i++){
if (head!=null){
stack.push(head);
head = head.next;
}else {
flag = true;
break;
}
}
if (flag){
while (stack.size()!=1){
stack.pop();
}
return stack.pop();
}
else {
ListNode temp = stack.pop();
ListNode newHead = temp;
while (stack.size()!=0){
temp.next = stack.pop();
temp = temp.next;
}
temp.next = reverseKGroup(head==null?null:head,k);
return newHead;
}
}
2.3方法三:递归
public ListNode reverseKGroup(ListNode head, int k) {
int l = k;
if (head == null) {
return null;
}
ListNode tail = head;
// 遍历到第k个节点
while (l > 1) {
tail = tail.next;
l--;
// 如果已经到达链表末尾,说明不够k个节点,此时不翻转,直接返回
if (tail == null) {
return head;
}
}
ListNode nextKHead = tail.next;
// 对此K个节点翻转
reverse(head, tail);
// 翻转后原来头结点变成尾节点,连接下一组
head.next = reverseKGroup(nextKHead, k);
return tail;
}
/**
* 对一段链表进行翻转
* @param start 头结点
* @param end 尾节点
* @return
*/
public ListNode reverse(ListNode start, ListNode end) {
ListNode dummy = new ListNode(0);
dummy.next = start;
ListNode pre = dummy, cur = start;
while (cur != end) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
cur.next = pre;
return end;
}
网友评论