[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – N번째 리스트 구하기

Given a singly linked list, devise a time- and space-efficient algorithm to find the mth-to-last element of the list. Implement your algorithm, taking care to handle relevant error conditions. Define mth to last such that when m = 0, the last element of the list is returned.

 

Limitations are below:

1] O(n) Time Complexity

2] O(1) space Complexity

 

solve] at first, I tried to travel twice. of course, it is very easy. but there is a better solution.

Just scan once. The main algorithm is very easy. just after kth node, traveling kth_node from head together. when list node reach the tail node, kth_node can reach kth_node.

 


void travel(int k){
 List *list = head;
 List *kth_node = head;
 int count = 0;
 while( list != NULL ){
 printf("(%d)\n", list->value);
 if( count > k ){
 kth_node = kth_node->next;
 }
 list = list->next;
 count++;
 }
 printf("(%d)th node from end is (%d)\n", k, kth_node->value );
 }