Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

The title

Enter the head node of a linked list and print out the value of each node from end to end.

Review key points

Features of linked lists, traversal of linked lists, access to linked lists

Your own train of thought

When I saw this topic, the first thing that came to mind was to use a stack to print a linked list from end to end. When we iterate over a linked list, we put the nodes we iterate over on the stack; The top element is then accessed and pushed off the stack.

And then the idea is to flip the linked list, which means that every time we access a node, we point that node’s next pointer to its previous node; Then iterate over the flipped list, and you can output the list from end to end.

code

preparation

Linked list node class

 class ListNode {
     int value;
     ListNode next;
 }
Copy the code

Data preparation

public class LinkedList { public ListNode head = new ListNode(-1); public static void main(String[] args) { LinkedList list = new LinkedList(); ListNode l1 = new ListNode(1); ListNode l2 = new ListNode(3); ListNode l3 = new ListNode(5); ListNode l4 = new ListNode(7); ListNode l5 = new ListNode(9); list.head.next = l1; l1.next = l2; l2.next = l3; l3.next = l4; l4.next = l5; list.printLinkedListReverselyByStack(); }}Copy the code

Implementation method based on flipped list

Every time a node is accessed, the next pointer of that node points to its previous node, and then the data of each node in the flipped list is iterated

Space-time complexity: O(1) space complexity, O(n) time complexity

Advantages: Less memory usage

Disadvantages: changed the structure of the original linked list, complex code, not easy to understand

Public void printLinedListReverselyByOverturn () {/ / to get the head node ListNode p = this. The head; ListNode q = p; ListNode q = p; ListNode next = p.next; ListNode next = p.next; Q.next = null; // continue while (next!) as long as the next node is not empty = null) {p = next; next = p.next; p.next = q; q = p; } // Change the header to this.head. Next = q; // iterate over the flipped list while (q! = null) { if (q.value == -1) return; System.out.print(q.value + " "); q = q.next; } System.out.println(); }Copy the code

Implementation based on stack

Each time a node is accessed, the data in that node is placed on the stack, and the data in the stack is iterated again

Space-time complexity: O(n) space complexity, O(n) time complexity

Advantages: clear thinking, less code, simple structure, easy to understand

Disadvantages: it will open up the memory space corresponding to the number of nodes, with O(N) space complexity

Public void printLinkedListReverselyByStack () {/ / to get the head node ListNode p = this. The head; // Create a Stack Stack<Integer> Stack = new Stack<>(); // Walk through the list and store the data on the stack while (p.ext! = null) { p = p.next; stack.push(p.value); } // iterate through the stack and fetch the top element until the stack is empty. stack.isEmpty()) { System.out.print(stack.pop() + " "); } System.out.println(); }Copy the code

Implementation based on recursion

Whenever we want to access a node, we print the data in the node after it, and then print the data in the current node.

Space-time complexity: O(n) space complexity, O(n) time complexity

Advantages: less code, simple implementation, easy to understand, do not change the structure of the original linked list.

Disadvantages: When there are too many nodes in the linked list, it will lead to deeper recursive levels, increasing memory footprint, O(N) space complexity, and may lead to memory overflow.

Public void printLinkedListByRecurrence () {/ / to get the head node ListNode p = this. The head; if (p.next ! = null) printLinkedListByRecurrence2(p.next); } public void printLinkedListByRecurrence2 (ListNode node) {/ / when the node is empty, the recursive began to return to the if (node! = null) {/ / when the node is not null, it prints the next point to nodes of printLinkedListByRecurrence2 (node. Next); System.out.print(node.value + ""); }}Copy the code

conclusion

How to walk through a linked list Also look at our use of stack data structures; Let’s examine our understanding of recursion. In general, we should try to avoid recursion in programming, because it will open up a lot of stack memory, function call and return, when the amount of data is very large, the performance is very low.