This blog is relatively simple. Just look at the reverse order of single linked lists if you don’t understand.
Reverse order idea
Now assume there is a linked list, which is to be operated in reverse order. The first thing we think of is to reverse the pointer relationship.
In fact, that's it. The blogger is a single linked list reverse order operation with this goal.
Node pre = null;Node post = null;while(head!=null){ post = head.next; head.next = pre; pre = head; head = post;}This is the core of reverse order. Let’s explain step by step.
At the beginning, pre and post are set to null. This is necessary because after the line of code execution of head.next=pre, the next of our original head node will become null, that is, the null of our entire linked list.
Imagine that the next at the end of the original link list is also a null? The truth here is the same.
At this time, updating pre to the original head node is also to prepare for the next step of reverse order, and the head naturally becomes the original head.next.
Sorry, my hand trembled and I drew it wrong. Thank you everyone. The fifth time on the hand-drawn diagram indicates that the pre node should be at the position of node 5 and there is no head.
It is not difficult to see from the legend that we move the head backward again and again, and update the pre node at the same time to achieve the effect of reverse order.
Code
package list;public class ReverseList {public static void main(String[] args) {Node head = new Node(1);int[] value = {2,3,4,5};Node temp = head;for (int i = 0 ; i< value.length;i++) {Node node = new Node(value[i]);temp.next = node;temp = temp.next;}printList(head);// Inverse the order of output a single linked list head = reverse(head);printList(head);// Reverse the head again = reverseSingleList(head);printList(head);}public static void printList(Node head) {while(head!=null) {System.out.print("/t"+head.value);head = head.next;}System.out.println();}public static Node reverse(Node head) {Node pre = null;Node post = null;while(head!=null) {post = head.next;head.next = pre;pre = head;head = post;}return pre;}public static Node reverseSingleList(Node head) {Node pre = null;Node next = null;while(head!=null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}}class Node {public int value;public Node next;public Node(int value) {this.value = value;}}test
After testing, the code output is correct.
1 2 3 4 5
5 4 3 2 1
1 2 3 4 5
To help understand, here is another example:
/** * java implements reverse order of single linked lists* @author Administrator * */public class SingleLinkedReverse {class Node{int data;Node next;public Node(int data){this.data = data;}}public static void main(String[] args) {SingleLinkedReverse slr = new SingleLinkedReverse();Node head, tail;head = tail = slr.new Node(0);for (int i=1; i<10; i++){Node p = slr.new Node(i);tail.next = p;tail = p;}tail = head;while(tail != null){System.out.print(tail.data+" ");tail = tail.next;}head = reverse(head);System.out.println(" "); while(head != null){System.out.print(head.data+" ");head = head.next;}}private static Node reverse(Node head) {Node p1,p2 = null;p1 = head;while(head.next != null){p2 = head.next;head.next = p2.next;p2.next = p1;p1 = p2;}return p2;}}Test results:
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
Summarize
The above is the entire content of this article about the code example of reverse order usage of Java single linked lists. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!