java单链表逆序用法代码示例

2024-07-13 10:17:21

字体：大中小

来源：转载

供稿：网友

本篇博客，比较简单。对单链表逆序不理解的看看就可以了。

逆序思想

现假设有一链表，有待逆序操作。我们首先想到的就是将那个指针关系逆序了就行了呗。

事实上，就是这样。博主就是以这个为目标来完成的单链表逆序操作。

javascript/59172.html">java;">Node pre = null;Node post = null;while(head!=null){ post = head.next; head.next = pre; pre = head; head = post;}

这便是逆序的核心了。下面我们就来一步步的讲解。

首次逆序：

一开始的话，pre，post都设置为null。这是必须的，因为在head.next=pre这行代码执行完成后，我们原始的那个head节点的next将变成null，也就是我们整个链表的null了。

想象一下，原来的那个链表的最后面的next不也是一个null吗？这里道理是一致的。

此时，更新pre为原来的head节点，也是为了下一步的逆序做准备，而head也自然的变成了原来的head.next了。

不断逆序。

java,单链表,逆序,java单链表逆序解释,单链表的逆序,单链表逆序输出

抱歉，手抖了一下，画错了。大家见谅。手绘图上的第五次示意pre节点应该在节点5的位置，没有了head。

从图例中我们也不难看出，我们就是一次次的将head向后移，同时更新pre节点，来达到逆序的效果。

代码

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);		// 反序输出一个单链表		head = reverse(head);		printList(head);		// 再次反向		head = 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;	}}

测试

经测试，代码输出正确。

1 2 3 4 5
5 4 3 2 1
1 2 3 4 5

帮助理解，下面是另一个实例：

/**  * java 实现单链表的逆序  * @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;	}}

测试结果：