Problem 1024,(Reverse a singly linked list and compute the sum of it Primary lev

Question

Problem 1024,(Reverse a singly linked list and compute the sum of it Primary level) http:Wacm.zjn 1: Introduction Problem description and (if any) background of the algorithms. Description ,,, , , vpedef int Elem Type; typedef struct LNode Elem Type data; struct LNode next; LNode, LinkedList First, create a singly linked list based on inputted elements; Then, reverse it; and output all elements in the reversed list; Finally, output the sum of all elements in it. Tips: use a singly linked list with a dummy head node. Input: n, n, First line: integer n, denoting the length of the singly linked list; Second line: n integers (elements) of the linked list one by one. Output: , Fist line: all elements of the reversed linked list one by one. Second line: The sum of all elements in the linked list. Sample Input 12345 Sample Output 54321 15 2: Algorithm Specification Description (pseudo-code preferred) of all the algorithms involved for solving the problem, including specifications of main data structures. 3: Testing Results Table of test cases. Each test case usually consists of a brief description of the purpose of this case, the expected result, the actual behavior of your program, the possible cause of a bug if your program does not function as expected, and the current status (pass" or "corrected", or "pending"). 4: Analysis and Comments Analysis of the time and space complexities of the algorithms. Appendix: Source Code (in C/C++) At least 30% of the lines must be commented. Otherwise the code will NOT be evaluated

Explanation / Answer

//As per the chegg guideline, please repost the Question number 1035 and 1025 in separate question ad each question itself contains 4 subparts and its will not get completed in the predefined time and please translate non-English statements to English//

//c code for reverse and sum of link list

#include<stdio.h>
struct LNode // create LNode
{
int data;
struct LNode* next;
};

void InsertLNode(struct LNode** head_ref, int NewNum) //Insert funtion to LNode
{
struct LNode* NewLNode =(struct LNode*) malloc(sizeof(struct LNode));
NewLNode->data = NewNum;
NewLNode->next = (*head_ref);   
(*head_ref) = NewLNode;
}

static void ListRreverse(struct LNode** head_ref) //reverse the linked list
{
struct LNode* previous = NULL;
struct LNode* current = *head_ref;
struct LNode* next = NULL;
while (current != NULL) //reverse process
{
next = current->next;  
current->next = previous;
previous = current;
current = next;
}
*head_ref = previous;
}

void print(struct LNode *head) //Print function
{
struct LNode *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);   
temp = temp->next;  
}
}   

int main()
{
/* Start with the empty list */
struct LNode* head = NULL;
int i=0,j,input,sum=0;

printf("how many number you want to insert in link list?");
scanf("%d",&j);
printf("input = %d ",j);
while(i<j){
printf("input number %d = ",i+1);
scanf("%d",&input);
sum=sum+input;
InsertLNode(&head,input );
i++;
}
printf("inserted list ");
print(head);   
ListRreverse(&head);   
printf(" Reversed list ");
print(head);
printf(" Total sum = %d",sum);

}

-------------------------------------------------

Pseudo code for reversed link list:

1. declare three pointer variable as Previous=NULL, Current as head and Next=NULL.
2. Loop trough the linked list and perform below operation:
next = curr->next (store next node before changing next of Current)
curr->next = prev (this is where reversing is done by changing next of current)
prev = curr (shift Previoust by one step)
curr = next (shift Current by one step)

Main Data structure- Linked List

It stores data linearly, where order is not mention by their physical location in memory. Each element stores reference to the next data element. In this singly linked list, each of data node contains: data, and a link or reference to the next node inside the sequence.

---------------------------------------------------------------

test results:

performed as per the direction, run the program to verify with your own data set

------------------------------------------------------------------

Time complexity is O(n) as the loop that iterates in the algorithm performs one way operation per cycle and contains no other loop.

Space complexity is O(1) as only 1 temporary variable is used for operational purpose. All other momory required to store actual data.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.