Linked list printing (linked list inversion output)

1. Title Description:
Enter the head node of a linked list and print the value of each node from tail to head. The linked list is defined as follows:

struct ListNode
{
	int m_nKey;
	ListNode* m_pNext;
}

2. Test case

  • Function test (the input linked list has multiple nodes; the input linked list has only one node)
  • Special input test (the input chain header node pointer is NULL)

3. Solution ideas
Idea 1: traverse the linked list, then save the data of the linked list in the array in turn, and then just output the data in the array in reverse order according to the array subscript. Equivalent to two iterations.
Complexity analysis: time complexity 0(n), space complexity 0(n)
The code is as follows:

void Linked_List_Reversal(ListNode* head)
{
	int res[100];
	int i = 0;
	while(head != NULL)
	{
		res[i++] = head->data;
		head = head->next;
	}
	while(i != 0)
	{
		printf("%d", res[i--]);
	}
	printf("\n");
}

Idea 2: traverse the linked list from beginning to end, and the output required by the topic is from end to end. That is, the first traversed node is the last output, and the last traversed node is the first output. In fact, it is LIFO, which is similar to the operation of stack, so we can consider using stack. After traversing the entire linked list, the values of nodes are output one by one from the top of the stack.
Complexity analysis:

void PrintListReversingly_Iteratively(ListNode* pHead)
{
	std::stack<ListNode*> nodes;
        ListNode* pNode = pHead;
        while(pNode != nullptr)
        {
        	nodes.push(pNode);
        	pNode = pNode->m_pNext;
        }
       while(!nodes.empty())
       {
		pNode = nodes.top();
               printf("%d\t", pNode->m_nValue);
               nodes.pop();
       }
}
//Note that there is no stack, push, pop and other operations in the C language. You can only write corresponding functions for definition. The process is complex, so this method is not recommended. Next, add stack definition and other functions
//Stack definition
typedef struct Stack
{
    int* arr;       //First address of storage stack
    int len;        //Stack length
    int top;        //Subscript at top of stack
}Stack;
//Create stack
Stack* create_stack(int len)
{
    Stack* stack = malloc(sizeof(Stack));
    stack->arr = malloc(siezof(int)*len);
    stack->len = len;
    stack->top = -1;
    return stack;
}
//Push 
bool push_stack(Stack* stack,int val)
{
    if(full_stack(stack))
        return false;
    stack->arr[++stack->top] = val;
    return true;
}
//Out of stack
bool pop_stack(Stack* stack)
{
    if(empty_stack(stack))
        return false;
    stack->top--;
    return true;
}
//Determine whether the stack is full
bool full_stack(Stack* stack)
{
    return stack->top + 1 >= stack->len;
}
//Determine whether the stack is empty
bool empty_stack(Stack* stack)
{
    return stack->top == -1;
}
//Display stack top
int top_stack(Stack* stack)
{
    if(!empty_stack(stack))
        return NULL;
    return stack->arr[stack->top];
}

Idea 3: the above mentioned stack implementation. In fact, recursion is also a stack operation, so recursion can also be used. To realize the reverse output of the linked list, when we visit a node, we first recursively output the node behind it, and then output the node itself, so as to realize the reverse printing of the linked list..
Complexity analysis:

void Listprint(ListNode* head)
{
    if(head!=NULL && head->next!=NULL)
    {
        Listprint(ListNode* head->next);
    }
    if(head!=NULL)  //Prevent empty linked list
    printf("%d\n",head->data);
}

Note: since time complexity and space complexity have not been carefully studied in the current study, time complexity and space complexity are not marked in some places, which will be added later if possible.

Keywords: Algorithm leetcode

Added by phillfox on Fri, 24 Dec 2021 12:24:58 +0200