Java逆序链表 + 判断链表是否成环(快慢指针)_java 判断是否有环

作业1 逆序链表

如果存在一个单链表，实现一个方法，给定这个单链表的头结点，获得这个链表经过反序之后链表的头结点

package cs.kaoyan.javase.com.list2;

public class Test {
    public static void main(String[] args) {
        //新建头结点,用头指针指向它
        Node head = new Node();
        head.next = null;

        //给头指针赋值
        head.data = 1;

        //cur表示当前结点(避免直接对头指针进行操作)
        Node cur = head;
        //tmp表示临时结点
        Node tmp = null;
        //新建链表 1 -> 2 -> 3 -> 4 -> 5
        for (int i = 2; i <= 5; i++) {
            //新建一个结点,用tmp指向它
            tmp = new Node();
            tmp.next = null;
            //赋值
            tmp.data = i;
            //连接链表
            cur.next = tmp;
            //修改当前指针的位置
            cur = tmp;
        }

        System.out.println("逆序之前:");
        //1 2 3 4 5 
        getList(head);

        //获取链表逆序之前的尾结点(该结点在逆序后成为新链表的头结点)
        Node tail = head;
        while (tail.next != null){
            tail = tail.next;
        }
        //逆序链表
        reverse(head);

        System.out.println("\n");
        System.out.println("逆序之后:");
        
        //这里要输入原链表的尾结点
        //5 4 3 2 1
        getList(tail);
    }

    //遍历链表
    public static void getList(Node head) {
        //先让tmp指针指向头结点
        Node tmp;
        tmp = head;
        while (tmp != null) {
            System.out.print(tmp.data + " ");
            tmp = tmp.next;
        }
    }

    public static Node reverse(Node head) {
        if (head == null || head.next == null) {
            //return null;
            //不需要逆序
            return head;
        }

        Node a = head;
        Node b = head.next;

        while (b != null) {
            Node c = b.next;
            b.next = a;
            a = b;
            b = c;
        }

        head.next = null;

        return a;

    }
}

class Node {
    int data;//数据域
    Node next;//指针域
}

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

作业2 判断链表是否成环

如果存在一个单链表，我们只拥有单链表的头结点，实现一个方法，判断链表中是否有环 (这个单链表的尾结点，它下一个指向，指向链表中的另外一个结点，构成一个环)

解题思路

定义两个指针，一个快指针fast，一个慢指针slow，快指针一次走两步，慢指针一次走一步，如果两个指针相遇了，则说明链表是有环的，如果fast走到null还没有相遇则说明没有环