Implement an algorithm to find the kth to last element of a singly linked list.
If we knew the length of the linked list, then we could just subtract k and we would move a pointer length-k times.
Here, I think the best way would be to just iterate through the linked list with two pointers. The two nodes start on the head of the linked list. The first pointer would go ahead k steps, and then both would move ahead until the first point touches the last node. The next node that the second node stops at will be out kth to last node.
This would take O(n) time since we have to go through all the elements of the linked list, and O(1) space.
Here's what I have:
We first create the structures for a linked list
If we knew the length of the linked list, then we could just subtract k and we would move a pointer length-k times.
Here, I think the best way would be to just iterate through the linked list with two pointers. The two nodes start on the head of the linked list. The first pointer would go ahead k steps, and then both would move ahead until the first point touches the last node. The next node that the second node stops at will be out kth to last node.
This would take O(n) time since we have to go through all the elements of the linked list, and O(1) space.
Here's what I have:
We first create the structures for a linked list
#include <stdlib.h>Then we make some linked list making functions
#include <stdio.h>
struct node{
int data;
struct node* next;
};
struct list{
struct node* head;
};
struct node* create_node(int data){
struct node* new_node = (struct node*)malloc(sizeof(struct node));
new_node->data = data;
new_node->next = NULL;
return new_node;
}
void add_node(struct list* llist,int data){
struct node* new_node = create_node(data);
new_node->next = llist->head;
llist->head = new_node;
}
The star method of this question! Assuming a valid k and linked list, we get two pointers, move the first k times, and then move both pointers until the first pointer reaches the end of the linked list.int kth_to_last(struct list* llist, int k){
struct node* tmp1 = llist->head;
struct node* tmp2 = llist->head;
int i;
for (i=0;i<k+1;i++){
tmp2 = tmp2->next;
}
while(tmp2->next != NULL){
tmp1 = tmp1->next;
tmp2 = tmp2->next;
}
return tmp1->data;
}
Then we create a linked list for some testinggggint main(int argc, char* argv[]){
struct list* new_list = (struct list*)malloc(sizeof(struct list));
new_list->head = NULL;
int i;
for (i=20;i>0;i--){
add_node(new_list, i*2);
}
for(i=0;i<19;i++){
printf("%ith item: %i\n", i+1, kth_to_last(new_list, i));
}
}
): renames a relation or an attribute.
