-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0025.c
92 lines (88 loc) · 2.21 KB
/
q0025.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//
// q0025.c
// LeetCode
//
// Created by NowOrNever on 22/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0025.h"
#include "../common.h"
//25. Reverse Nodes in k-Group
//Hard
//808
//182
//
//
//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.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
if (head == NULL) {
return head;
}
struct ListNode **lists = calloc(k, sizeof(struct ListNode *));
struct ListNode *p = head;
struct ListNode *lastTail = NULL;
struct ListNode *result = NULL;
int count = 0;
while (p != NULL) {
lists[count++] = p;
p = p->next;
if (count == k) {
if (lastTail) {
lastTail->next = lists[k-1];
}else if (result == NULL){
result = lists[count - 1];
}
for (int i = k - 1; i > 0 ; i--) {
lists[i]->next = lists[i - 1];
}
lastTail = lists[0];
count = 0;
// printList(result);
}
}
if (count) {
if (lastTail) {
lastTail->next = lists[0];
}
if (result == NULL) {
result = lists[0];
}
}else{
lists[0]->next = NULL;
}
return result;
}
int question25(){
int size = 1;
int testArray[size];
for (int i = 0; i < size; i++) {
testArray[i] = i + 1;
}
struct ListNode *result = intArrayToList(testArray, size);
printList(result);
result = reverseKGroup(result, 2);
printList(result);
return 0;
}