图示：
代码：
1 import lombok.Data;
2 import java.util.Stack;
3
4 public class SingleLinkedListTest {
5 public static void main(String[] args) {
6 SingleNode node1 = new SingleNode(1, "宋江");
7 SingleNode node2 = new SingleNode(2, "卢俊义");
8 SingleNode node3 = new SingleNode(3, "吴用");
9 SingleNode node4 = new SingleNode(4, "林冲");
10 //创建单链表
11 SingleLinkedList singleLinkedList = new SingleLinkedList();
12 System.out.println(singleLinkedList.isEmpty());
13 //添加
14 // singleLinkedList.tailInsert(node1);
15 // singleLinkedList.tailInsert(node4);
16 // singleLinkedList.tailInsert(node2);
17 // singleLinkedList.tailInsert(node3);
18 singleLinkedList.orderInsert(node1);
19 singleLinkedList.orderInsert(node4);
20 singleLinkedList.orderInsert(node2);
21 singleLinkedList.orderInsert(node3);
22 System.out.println(singleLinkedList.isEmpty());
23 System.out.println(singleLinkedList.toString());
24
25 // SingleNode node5 = new SingleNode(2, "玉麒麟");
26 // singleLinkedList.updateByNo(node5);
27 // System.out.println(singleLinkedList.toString());
28
29 // singleLinkedList.delByNo(4);
30 // System.out.println(singleLinkedList.toString());
31
32 // singleLinkedList.reversePrint();
33
34 // singleLinkedList.reverseList();
35 // System.out.println(singleLinkedList.toString());
36
37 // System.out.println(singleLinkedList.size());
38
39 SingleNode lastIndexNode = singleLinkedList.findLastIndexNode(5);
40 System.out.println(lastIndexNode);
41 }
42 }
43
44
45 @Data
46 class SingleNode {
47
48 /**
49 * 编号
50 */
51 private int no;
52
53 /**
54 * 名称
55 */
56 private String name;
57
58 private SingleNode next;
59
60 public SingleNode() {
61
62 }
63
64 public SingleNode(int no, String name) {
65 this.no = no;
66 this.name = name;
67 }
68
69 }
70
71 class SingleLinkedList {
72 private SingleNode headNode;
73
74 public SingleLinkedList() {
75 this.headNode = new SingleNode();
76 }
77
78 /**
79 * 判断单链表是否为空
80 * @return
81 */
82 public boolean isEmpty() {
83 return headNode.getNext() == null;
84 }
85
86 /**
87 * 尾部添加节点
88 * @param newNode
89 * @return
90 */
91 public boolean tailInsert(SingleNode newNode) {
92 SingleNode temp = headNode;
93 while (true) {
94 if (temp.getNext() == null) {
95 temp.setNext(newNode);
96 break;
97 }
98 temp = temp.getNext();
99 }
100 return true;
101 }
102
103 /**
104 * 按编号顺序插入
105 * @param newNode
106 * @return
107 */
108 public boolean orderInsert(SingleNode newNode) {
109 SingleNode temp = headNode;
110
111 while (true) {
112 if (temp.getNext() == null) {
113 temp.setNext(newNode);
114 return true;
115 }
116 if (temp.getNext().getNo() == newNode.getNo()) {
117 System.out.println("存在编号相同的节点，无法插入");
118 return false;
119 }
120
121 if (temp.getNext().getNo() > newNode.getNo()) {
122 newNode.setNext(temp.getNext());
123 temp.setNext(newNode);
124 return true;
125 }
126 temp = temp.getNext();
127 }
128 }
129
130 /**
131 * 根据编号修改节点
132 * @param newNode
133 * @return
134 */
135 public boolean updateByNo(SingleNode newNode) {
136 SingleNode temp = headNode.getNext();
137
138 while (true) {
139 if (temp == null) {
140 System.out.println("未找到需修改的节点");
141 return false;
142 }
143
144 if (temp.getNo() == newNode.getNo()) {
145 temp.setName(newNode.getName());
146 return true;
147 }
148 temp = temp.getNext();
149 }
150 }
151
152 /**
153 * 根据编号删除
154 * @param no
155 * @return
156 */
157 public boolean delByNo(int no) {
158 SingleNode temp = headNode;
159
160 while (true) {
161 if (temp.getNext() == null) {
162 System.out.println("未找到需删除的节点");
163 return false;
164 }
165 if (temp.getNext().getNo() == no) {
166 temp.setNext(temp.getNext().getNext());
167 return true;
168 }
169 temp = temp.getNext();
170 }
171 }
172
173 /**
174 * 逆序打印
175 */
176 public void reversePrint() {
177 //通过栈的特性进行逆序打印
178 Stack<SingleNode> singleNodeStack = new Stack<>();
179
180 SingleNode temp = headNode.getNext();
181 while (true) {
182 if (temp == null) {
183 break;
184 }
185 singleNodeStack.push(temp);
186 temp = temp.getNext();
187 }
188
189 while (singleNodeStack.size() > 0) {
190 System.out.println(singleNodeStack.pop());
191 }
192 }
193
194 /**
195 * 反转单链表
196 * @return
197 */
198 public boolean reverseList() {
199 //链表为空或者只有一个元素，不需要反转
200 if (headNode.getNext() == null || headNode.getNext().getNext() == null) {
201 return true;
202 }
203 //创建一个临时的头节点
204 SingleNode tempHead = new SingleNode();
205 //当前处理的节点
206 SingleNode currNode = headNode.getNext();
207 //下一个要处理的节点
208 SingleNode nextNode = null;
209 //画图演示这个过程
210 while (currNode != null) {
211 nextNode = currNode.getNext();
212 currNode.setNext(tempHead.getNext());
213 tempHead.setNext(currNode);
214 currNode = nextNode;
215 }
216 //将反转后的链表重新赋给头节点
217 headNode.setNext(tempHead.getNext());
218 return true;
219 }
220
221 /**
222 * 单链表的长度
223 * @return
224 */
225 public int size() {
226 SingleNode temp = headNode.getNext();
227 //统计不包含头节点
228 int count = 0;
229 while (temp != null) {
230 count++;
231 temp = temp.getNext();
232 }
233 return count;
234 }
235
236 /**
237 * 查找倒数第index的节点
238 * @param index
239 * @return
240 */
241 public SingleNode findLastIndexNode(int index) {
242 if (isEmpty()) {
243 System.out.println("单链表为空");
244 return null;
245 }
246
247 int size = size();
248 if (index <= 0 || index > size) {
249 System.out.println("index输入不合理");
250 return null;
251 }
252
253 SingleNode temp = headNode.getNext();
254 //temp向后走（size - index）就是需要查找的节点
255 for (int i = 0; i < size - index; i++) {
256 temp = temp.getNext();
257 }
258 return temp;
259 }
260
261 @Override
262 public String toString() {
263 return "SingleLinkedList{" +
264 "headNode=" + headNode +
265 '}';
266 }
267 }
标签：getNext,SingleNode,单链,return,temp,headNode,singleLinkedList From： https://www.cnblogs.com/xueseng/p/17040295.html