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

时间:2021-09-27 05:49:15

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

逆序思想

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

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

java" id="highlighter_702464">
?
1
2
3
4
5
6
7
8
9
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单链表逆序用法代码示例

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

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

代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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

帮助理解,下面是另一个实例:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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;
    }
}

测试结果:

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

总结

以上就是本文关于java单链表逆序用法代码示例的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/marksinoberg/article/details/52490318