leetcode 25번 정리
leetcode25번을 푸는데.. 아래와 같이 풀면.. 내 PC에서 빌드는 잘되고 값도 잘 나오는데.. ㅡ.ㅡ;
#if 0
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.
#endif
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//insert to head next
//insert to last point
#include
#include
struct ListNode{
int val;
struct ListNode *next;
};
void add_after_head(struct ListNode* root, int value)
{
struct ListNode* add = malloc(sizeof(struct ListNode));
add->val = value;
add-> next = root->next;
root->next = add;
}
void add_last_geeks(struct ListNode** head_ref, int value)
{
struct ListNode* new_node = malloc(sizeof(struct ListNode));
struct ListNode* last = *head_ref;
new_node->val = value;
new_node->next = NULL;
if(*head_ref == NULL)
{
*head_ref = new_node;
return ;
}
while(last->next != NULL)
{
last = last->next;
}
last->next = new_node;
return;
}
struct ListNode* add_last(struct ListNode* root, int value)
{
struct ListNode* result = malloc(sizeof(struct ListNode));
result->next = root;
if(root == NULL)
return NULL;
while(root->next != NULL)
root = root->next;
struct ListNode* add = malloc(sizeof(struct ListNode));
add->val = value;
add-> next = NULL;
root->next = add;
return result->next;
}
void print_linkedlist(struct ListNode* root)
{
printf(“linkedlist “);
while(root != NULL)
{
printf(“%d “, root->val);
root = root->next;
}
printf(“\n”);
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
struct ListNode* result_head = malloc(sizeof(struct ListNode));
struct ListNode* result = malloc(sizeof(struct ListNode));
struct ListNode* next = malloc(sizeof(struct ListNode));
// next->val = 0;
// next->next = NULL;
// result->next = next;
result_head = result;
struct ListNode* head_tmp = malloc(sizeof(struct ListNode));
head_tmp = head;
int count = 0;
int all_cnt =0;
if(head == NULL)
return NULL;
while(head_tmp != NULL)
{
if(count < k )
{
count++;
head_tmp = head_tmp->next;
}else
{
count = 0;
//insert k to result->next (k times)
//add_after_head
for(int i =0; i < k; i++)
{
add_after_head(result, head->val);
head = head->next;
all_cnt++;
}
for(int i =0; i < k; i++)
{
result = result->next;
}
}
}
if(count == k)
{
count = 0;
//insert k to result->next (k times)
//add_after_head
for(int i =0; i < k; i++)
{
add_after_head(result, head->val);
head = head->next;
}
}
if(count != 0)
{
// all_cnt 이후에 나머지를 add_last를 이용해서 넣는다.
//head = add_last(head, value)
for(int i =0; i < count; i++)
{
result = add_last(result, head->val);
// if(i ==0)
// { result->next-> val = result->next->next->val;
// result-> next = result->next->next;
// }
//add_last_geeks(&result, head->val);
head = head->next;
}
}
return result_head->next;
}
int main(int argc, char*argv[])
{
struct ListNode* root = malloc(sizeof(struct ListNode));
root->next = NULL;
//1->2->3->4->5
root = add_last(root, 1);
root = add_last(root, 2);
root = add_last(root, 3);
root = add_last(root, 4);
root = add_last(root, 5);
// add_last_geeks(&root, 1);
// add_last_geeks(&root, 2);
// add_last_geeks(&root, 3);
// add_last_geeks(&root, 4);
// add_last_geeks(&root, 5);
print_linkedlist(root->next);
root = reverseKGroup(root->next, 3);
print_linkedlist(root);
// add_last_geeks(&root, 1);
// add_after_head(root, 1);
return 0;
}
leetcode에서 돌리면 아래와 같은 문제가 발생한다.
움.. NULL로 초기화 하지않아서 발생하는것 같은데.. 초기화를 하게 되면 이상하게 linked list의 val값에 0이 들어가서 오답이 된다.
하아.. 궁굼하네ㅡ.ㅡ
움.. 이 문제는.. 결국.. 초기화 이슈였다 ㅡ.ㅡ;
아래는 수정한 버젼이다 ^^;
#if 0
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.
#endif
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//insert to head next
//insert to last point
#include
#include
struct ListNode{
int val;
struct ListNode *next;
};
void add_after_head(struct ListNode* root, int value)
{
struct ListNode* add = malloc(sizeof(struct ListNode));
add->val = value;
add-> next = root->next;
root->next = add;
}
void add_last(struct ListNode* root, int value)
{
struct ListNode* last = NULL;
if(root == NULL)
return ;
last = root;
while(last->next != NULL)
last = last->next;
last->next = malloc(sizeof(struct ListNode));
last->next->val = value;
last->next->next = NULL;
}
void print_linkedlist(struct ListNode* root)
{
printf(“linkedlist “);
while(root != NULL)
{
printf(“%d “, root->val);
root = root->next;
}
printf(“\n”);
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
struct ListNode* result_head = NULL;//malloc(sizeof(struct ListNode));
struct ListNode* result = malloc(sizeof(struct ListNode));
result->next = NULL;
result_head = result;
struct ListNode* node = head;
int count = 0;
int all_cnt =0;
if(head == NULL)
return NULL;
while(node != NULL)
{
if(count < k )
{
count++;
node = node->next;
}
else
{
count = 0;
for(int i =0; i < k; i++)
{
add_after_head(result, head->val);
head = head->next;
all_cnt++;
}
for(int i =0; i < k; i++)
{
result = result->next;
}
}
}
if(count == k)
{
count = 0;
for(int i =0; i < k; i++)
{
add_after_head(result, head->val);
head = head->next;
}
}
if(count != 0)
{
for(int i =0; i < count; i++)
{
add_last(result, head->val);
head = head->next;
}
}
return result_head->next;
}
int main(int argc, char*argv[])
{
struct ListNode* root = malloc(sizeof(struct ListNode));
root->next = NULL;
//1->2->3->4->5
add_last(root, 1);
add_last(root, 2);
add_last(root, 3);
add_last(root, 4);
add_last(root, 5);
// add_last_geeks(&root, 1);
// add_last_geeks(&root, 2);
// add_last_geeks(&root, 3);
// add_last_geeks(&root, 4);
// add_last_geeks(&root, 5);
print_linkedlist(root->next);
root = reverseKGroup(root->next, 2);
print_linkedlist(root);
// add_last_geeks(&root, 1);
// add_after_head(root, 1);
return 0;
}
\