数据结构第一节之单链表，看完即可去刷题_数据结构是看一章刷一章题还是看完再刷题

数据结构第一节之单链表，看完即可去刷题

下面的代码讲述了从创建到应用的过程。
//链表中节点的结构
class Node {
public int val;
public Node next;
public Node() {

}
public Node(int val) {
    this.val = val;
}
1
2
3
4

}
//链表的创建
public class MyLinkedList {

public Node head;//表示当前链表的头 默认是null

/**
 *
 */
public void createLinked() {
    this.head = new Node(12);
    Node node2 = new Node(22);
    Node node3 = new Node(32);
    Node node4 = new Node(42);
    this.head.next = node2;
    node2.next = node3;
    node3.next = node4;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//打印链表
public void display() {
Node cur = this.head;
while (cur != null) {
System.out.print (cur.val +" ");
//
cur = cur.next;
}
System.out.println();
}

/**
 * 从指定的位置newHead
 * 开始进行打印
 * @param newHead
 */
public void display(Node newHead) {
    Node cur = newHead;
    while (cur != null) {
        System.out.print (cur.val +" ");
        cur = cur.next;
    }
    System.out.println();
}


public Node findLastNode() {
    if(this.head == null) {
        System.out.println("head == null");
        return null;
    }
    Node cur = this.head;
    while (cur.next != null) {
        cur = cur.next;
    }
    return cur;
}

/**
 * 这个代码有瑕疵  改这个代码
 * @return
 */
public Node findLastTwoNode() {
    if(this.head == null) {
        System.out.println("想啥呢，什么都没有！");
        return null;
    }
    if(this.head.next == null) {
        System.out.println("想啥呢，只有1个节点！");
        return null;
    }
    Node cur = this.head;
    while (cur.next.next != null) {
        cur = cur.next;
    }
    return cur;
}

public Node findN(int n) {
    if(this.head == null) {
        System.out.println("单链表为空！");
        return null;
    }
    if(n <= 0) {
        System.out.println("n太小了！");
        return null;
    }
    if(n > size()) {
        System.out.println("n太大了");
        return null;
    }
    int count = 1;
    Node cur = this.head;
    while (count != n) {
        count++;//1
        cur = cur.next;
    }
    return cur;
}

//得到单链表的长度
public int size(){
    Node cur = this.head;
    int count = 0;
    while (cur != null) {
        count++;//2
        cur = cur.next;
    }
    return count;
}

//查找是否包含关键字key是否在单链表当中
public boolean contains(int key) {
    Node cur = this.head;
    while (cur != null) {
        if(cur.val == key) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

//头插法
public void addFirst(int data) {
    //0、首先你得有个节点
    Node node = new Node(data);
    //1、判断链表是不是空的
    if(this.head == null) {
        this.head = node;
    }else {
        //2、插入
        node.next = this.head;
        this.head = node;
    }
    //0、首先你得有个节点
   /* Node node = new Node(data);
    //1、判断链表是不是空的
    node.next = this.head;
    this.head = node;*/
}




//尾插法
public void addLast(int data) {
    //0、new
    Node node = new Node(data);
    if(this.head == null) {
        this.head = node;
    }else {
        //1、cur 找尾巴
        Node cur = this.head;
        while (cur.next != null) {
            cur = cur.next;
        }
        //2、插入
        cur.next = node;
    }
}

/**
 * 该函数是找到index-1位置的节点的引用
 * @param index
 * @return
 */
public Node moveIndex(int index) {
    Node cur = this.head;
    int count = 0;
    while (count != index-1) {
        cur = cur.next;
        count++;
    }
    return cur;
}

//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data) {
    if(index < 0 || index > size()) {
        System.out.println("index不合法");
        return;
    }
    //头插法
    if(index == 0) {
        addFirst(data);
        return;
    }
    //尾插法
    if(index == size()) {
        addLast(data);
        return;
    }
    Node cur = moveIndex(index);
    //cur保存的是 index-1位置的节点的引用
    Node node = new Node(data);
    node.next = cur.next;
    cur.next = node;
}

/**
 * 找到关键key的前驱，如果有返回前驱节点的引用
 * 如果没有返回null
 * @param key
 * @return
 */
public Node searchPrev(int key) {
    Node cur = this.head;

    while (cur.next != null) {
        if(cur.next.val == key) {
            return cur;
        }
        cur = cur.next;
    }
    return null;
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
    if(this.head == null) {
        return;
    }
    if(this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    Node prev = searchPrev(key);
    if(prev == null) {
        System.out.println("没有这个key的前驱");
    }else {
        Node del = prev.next;
        prev.next = del.next;
    }
}
//删除所有值为key的节点
public void removeAllKey(int key){
    Node prev = this.head;
    Node cur = prev.next;
    while (cur != null) {
        if(cur.val == key) {
            prev.next = cur.next;
        }else {
            prev = cur;
        }
        cur = cur.next;
    }
    if(this.head.val == key) {
        this.head = this.head.next;
    }
}


public void clear() {
    this.head = null;
}
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224

//翻转单链表
public Node reverseList() {
Node cur = this.head;
Node prev = null;
Node newHead = null;
while (cur != null) {
Node curNext = cur.next;
if(curNext == null) {
newHead = cur;
}
cur.next = prev;
prev = cur;
cur = curNext;
}
return newHead;
}

public Node reverseList2() {
    Node prev = null;
    while (head != null) {
        Node cur = this.head;
        this.head = head.next;
        cur.next = prev;
        prev = cur;
    }
    return prev;
}
public Node reverseList3() {
   Node cur = this.head;
   Node prev = null;
   while (cur != null) {
       Node curNext = cur.next;
       cur.next = prev;
       prev = cur;
       cur = curNext;
   }
   return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

//找到中间节点
public Node middleNode1() {
int len = size()/2;
Node cur = this.head;
int count = 0;
while (count != len) {
cur = cur.next;
count++;
}
return cur;
}

public Node middleNode() {
    Node fast = this.head;
    Node slow = this.head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9

以上就是单链表的所有代码，大家可根据此图来理解