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.