Homework Sourse1 Write a GetNth function that takes a linked list and an in
1) Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position. GetNth() uses the C numbering convention that the first node is index 0, the second is index 1, ... and so on. So for the list {42, 13, 666} GetNth() with index 1 should return 13. The index should be in the range [0..length-1]. If it is not, GetNth() should assert() fail (or you could implement some other error case strategy).
2)
Write a function – Split() which given a list, splits it into two sublists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list. So Split() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7,11}. Getting this right for all the cases is harder than it looks. You should check your solution against a few cases (length = 2, length = 3, length=4) to make sure that the list gets split correctly near the short-list boundary conditions. If it works right for length=4, it probably works right for length=1000. You will probably need special case code to deal with the (length <2) cases.
Hint. Probably the simplest strategy is to compute the length of the list, then use a for
loop to hop over the right number of nodes to find the last node of the front half, and then
cut the list at that point.
Solution
1)
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node * next;
};
struct node * BuildOneTwoThree(){
struct node * head = NULL;
struct node * second = NULL;
struct node * third = NULL;
head = malloc(sizeof(struct node));
second = malloc(sizeof(struct node));
third = malloc(sizeof(struct node));
head -> data = 1;
head -> next = second;
second -> data = 2;
second -> next = third;
third -> data = 3;
third -> next = NULL;
return head;
}
int ListLength(struct node* head){
int length = -1;
struct node * current = head;
while(current!=NULL){
length+=1;
current = current->next;
}
return length;
}
int GetNth(struct node *head, int index){
struct node * current;
int currentIndex = 0;
current = head;
while (current!=NULL)
{
if (currentIndex == index)
return current->data;
else
currentIndex+=1;
current = current->next;
}
}
int main()
{
int listLength,index,data;
struct node * head;
head = BuildOneTwoThree();
listLength = ListLength(head);
do{
printf(\"\ Enter the Linked List index:\ \");
scanf(\"%d\",&index);
if (listLength == -1)
printf(\"List could not be initialized\");
else if(listLength >= 0 && index <= listLength)
{
data = GetNth(head,index);
printf(\"\ The value at the given index %d is: %d.\ \",index,data);
}
else
printf(\"\ Please enter number within range 0 to %d\ \",listLength);
}
while (1);
return 1;
}
2)
void FrontBackSplit(Node *head, Node **front, Node **back) {
if (!head) return;
Node *front_last_node;
Node *slow = head;
Node *fast = head;
while (fast) {
front_last_node = slow;
slow = slow->next;
fast = (fast->next) ? fast->next->next : NULL;
}
front_last_node->next = NULL;
*front = head;
*back = slow;
}
