链表

一、单链表

1、单链表概述

链表是以节点的方式来存储,是链式存储
每个节点包含data域， next 域：指向下一个节点.
链表的各个节点不一定是连续存储
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确

2、面试题

1）有效节点个数

java

/**
 * 有效节点个数（遍历+计数）
 */
public int usedNode() {
    int ans = 0;
    heroNode temp = head;
    while (temp.next != null) {
        ans++;
        temp = temp.next;
    }
    return ans;
}

2）倒数第K个节点数据

java

/**
 * 反向输出第k个节点
 */
public void oppoShow(int k) {
    int all = usedNode();
    heroNode temp = head.next;
    if (all < k) {
        System.out.printf("没有第%d个节点\n", k);
        return;
    }
    int i = 1;
    while (temp != null) {
        if (i == (all - k + 1)) {
            System.out.println(temp.toString());
            break;
        }
        temp = temp.next;
        i++;
    }
}

3）反向遍历——迭代

java

/**
 * 反向遍历
 */
public void oppoShow() {
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    int all = usedNode();
    for (int i = all; i >= 0; i--) {
        int j = 1;
        heroNode temp = head.next;
        while (temp != null) {
            if (j == i) {
                System.out.println(temp.toString());
                break;
            }
            j++;
            temp = temp.next;
        }
    }
}

4）反向遍历——栈

java

class nodeStact {
	int maxSize;
	heroNode[] hn;
	int top;

	/**
	 * 栈的构造器
	 * 
	 * @param maxSize 栈的大小
	 */
	nodeStact(int maxSize) {
		this.maxSize = maxSize;
		hn = new heroNode[maxSize];
		top = -1;
	}

	/**
	 * 判空
	 */
	public boolean isEmpty() {
		return top == -1;
	}

	/**
	 * 判满
	 */
	public boolean isFull() {
		return top == maxSize - 1;
	}

	/**
	 * 弹出
	 */
	public heroNode pop() {
		if (isEmpty()) {
			System.out.println("栈空");
			return null;
		}
		return hn[top--];
	}

	/**
	 * 压栈
	 */
	public void push(heroNode _hn) {
		if (isFull()) {
			System.out.println("栈满");
		} else {
			hn[++top] = _hn;
		}
	}
}

java

/**
 * 反向遍历——通过栈实现
 */
public void showByStack() {
    if(head.next == null) {
        System.out.println("链表为空");
        return;
    }
    nodeStact ns = new nodeStact(usedNode());
    heroNode temp = head.next;
    while(temp != null) {
        ns.push(temp);
        temp = temp.next;
    }
    while(!ns.isEmpty()) {
        System.out.println(ns.pop().toString());
    }
}

5）合并单链表

java

/**
 * 与demo合并
 */
public void mesh() {
    singleLinkedList demo = new singleLinkedList();
    demo.add(new heroNode(-1, "小明", "王哥"));
    demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));
    heroNode temp = demo.head.next;
    while(temp != null) {
        addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));
        temp = temp.next;
    }

}

3、代码实现

java

package work.rexhao.linkedlist;

import java.util.Scanner;

public class singleLinkedListDemo {

	public static void main(String[] args) {
		singleLinkedList sll = new singleLinkedList();
		boolean loop = true;
		while (loop) {
			System.out.println("--------");
			System.out.println("1.在尾部添加");
			System.out.println("2.按编号添加");
			System.out.println("3.遍历单链表");
			System.out.println("4.修改节点");
			System.out.println("5.删除节点");
			System.out.println("6.有效节点个数");
			System.out.println("7.反向输出");
			System.out.println("8.反向遍历");
			System.out.println("0.退出");
			System.out.println("--------");
			Scanner sc = new Scanner(System.in);
			int key = sc.nextInt();
			if (key == 1) {
				System.out.println("请输入英雄编号：");
				int no = sc.nextInt();
				System.out.println("请输入英雄姓名：");
				Scanner sc1 = new Scanner(System.in);
				String name = sc1.nextLine();
				System.out.println("请输入英雄昵称：");
				Scanner sc2 = new Scanner(System.in);
				String nickName = sc2.nextLine();
				sll.add(new heroNode(no, name, nickName));
				System.out.println("添加成功！");
			} else if (key == 2) {
				System.out.println("请输入英雄编号：");
				int no = sc.nextInt();
				System.out.println("请输入英雄姓名：");
				Scanner sc1 = new Scanner(System.in);
				String name = sc1.nextLine();
				System.out.println("请输入英雄昵称：");
				Scanner sc2 = new Scanner(System.in);
				String nickName = sc2.nextLine();
				sll.addByNo(new heroNode(no, name, nickName));
				System.out.println("添加成功！");
			} else if (key == 3) {
				try {
					sll.show();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
			} else if (key == 4) {
				System.out.println("请输入英雄编号：");
				int no = sc.nextInt();
				System.out.println("请输入英雄新的姓名：");
				Scanner sc1 = new Scanner(System.in);
				String name = sc1.nextLine();
				System.out.println("请输入英雄新的昵称：");
				Scanner sc2 = new Scanner(System.in);
				String nickName = sc2.nextLine();
				sll.change(no, name, nickName);
			} else if (key == 5) {
				System.out.println("请输入英雄编号：");
				int no = sc.nextInt();
				sll.delete(no);
			} else if (key == 6) {
				System.out.println("有效节点个数：" + sll.usedNode());
			} else if (key == 7) {
				int k = sc.nextInt();
				sll.oppoShow(k);
			} else if (key == 8) {
				System.out.println("通过反向遍历实现：");
				sll.oppoShow();
				System.out.println("通过栈实现：");
				sll.showByStack();
			} else if (key == 9) {
				System.out.println("与demo链表合并");
				sll.mesh();
			} else if (key == 0) {
				loop = false;
			} else {
				System.out.println("输入有误！");
			}
		}
	}
}

/**
 * 管理英雄
 */
class singleLinkedList {
	/**
	 * 定义一个头结点
	 */
	private heroNode head = new heroNode(0, "", "");

	/**
	 * 添加节点的方法(尾插法) 将最后的next域指向新的node
	 */
	public void add(heroNode hn) {
		// 需要一个辅助变量
		heroNode temp = head;
		// 遍历单链表
		while (temp.next != null) {
			temp = temp.next;
		}
		// 退出循环时，temp指向最后
		temp.next = hn;
	}

	/**
	 * 按照编号大小添加
	 * 
	 * @param hn
	 */
	public void addByNo(heroNode hn) {
		/**
		 * 空链表：直接放后面
		 */
		if (head.next == null) {
			head.next = hn;
			return;
		}
		heroNode temp = head.next;
		/**
		 * 如果只有一个节点，且大于hn
		 */
		if (hn.getNo() < temp.getNo()) {
			head.next = hn;
			hn.next = temp;
			return;
		}
		while (true) {
			/**
			 * 如果no相等：报错
			 */

			if (hn.getNo() == temp.getNo()) {
				throw new RuntimeException("编号重复！");
			}
			if (temp.next != null) {
				if (hn.getNo() == temp.next.getNo()) {
					throw new RuntimeException("编号重复！");
				}
			}

			/**
			 * 找到：大于前一个节点且（小于后一个节点或者后一个节点为null）的节点
			 */
			if (hn.getNo() > temp.getNo() && (temp.next == null || hn.getNo() < temp.next.getNo())) {
				hn.next = temp.next;
				temp.next = hn;
				break;
			}
			if (temp.next != null) {
				temp = temp.next;
			} else {
				break;
			}
		}
	}

	/**
	 * 遍历
	 */
	public void show() {
		// 判空
		if (head.next == null) {
			throw new RuntimeException("链表为空");
		}
		// 遍历
		heroNode temp = head.next;
		while (temp != null) {
			System.out.println(temp.toString());
			temp = temp.next;
		}
	}

	/**
	 * 修改节点
	 */
	public void change(int no, String name, String nickName) {
		// 判空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 遍历：找no节点
		heroNode temp = head.next;
		while (temp != null) {
			if (temp.getNo() == no) {
				temp.setName(name);
				temp.setNickName(nickName);
				System.out.println("修改成功！");
				return;
			}
			temp = temp.next;
		}
		System.out.printf("未找到编号为%d的节点\n", no);
		return;
	}

	/**
	 * 删除节点
	 */
	public void delete(int no) {
		// 判空
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		// 遍历找节点
		heroNode temp = head;
		while (temp.next != null) {
			if (temp.next.getNo() == no) {
				temp.next = temp.next.next;
				System.out.println("删除成功");
				return;
			}
			temp = temp.next;
		}
		System.out.printf("未找到编号为%d的节点\n", no);
		return;
	}

	/**
	 * 有效节点个数（遍历+计数）
	 */
	public int usedNode() {
		int ans = 0;
		heroNode temp = head;
		while (temp.next != null) {
			ans++;
			temp = temp.next;
		}
		return ans;
	}

	/**
	 * 反向输出第k个节点
	 */
	public void oppoShow(int k) {
		int all = usedNode();
		heroNode temp = head.next;
		if (all < k) {
			System.out.printf("没有第%d个节点\n", k);
			return;
		}
		int i = 1;
		while (temp != null) {
			if (i == (all - k + 1)) {
				System.out.println(temp.toString());
				break;
			}
			temp = temp.next;
			i++;
		}
		return;
	}

	/**
	 * 反向遍历——翻转单链表
	 */
	public void oppoShow() {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		int all = usedNode();
		for (int i = all; i >= 0; i--) {
			int j = 1;
			heroNode temp = head.next;
			while (temp != null) {
				if (j == i) {
					System.out.println(temp.toString());
					break;
				}
				j++;
				temp = temp.next;
			}
		}
	}

	/**
	 * 反向遍历——通过栈实现
	 */
	public void showByStack() {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		nodeStact ns = new nodeStact(usedNode());
		heroNode temp = head.next;
		while (temp != null) {
			ns.push(temp);
			temp = temp.next;
		}
		while (!ns.isEmpty()) {
			System.out.println(ns.pop().toString());
		}
	}
	
	/**
	 * 与demo合并
	 */
	public void mesh() {
		singleLinkedList demo = new singleLinkedList();
		demo.add(new heroNode(-1, "小明", "王哥"));
		demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));
		heroNode temp = demo.head.next;
		while(temp != null) {
			addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));
			temp = temp.next;
		}
		
	}
}

/**
 * 定义heroNode节点
 */
class heroNode {
	private int no;
	private String name;
	private String nickName;
	public heroNode next;

	/**
	 * 构造器
	 * 
	 * @param no       编号
	 * @param name     姓名
	 * @param nickName 昵称
	 */
	heroNode(int no, String name, String nickName) {
		this.name = name;
		this.no = no;
		this.nickName = nickName;
	}

	/**
	 * 重写toString
	 */
	@Override
	public String toString() {
		return "[no=" + no + ", name=" + name + ", nickName=" + nickName + ", next=" + next + "]";
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public String getNickName() {
		return nickName;
	}

	public void setNickName(String nickName) {
		this.nickName = nickName;
	}

}

class nodeStact {
	int maxSize;
	heroNode[] hn;
	int top;

	/**
	 * 栈的构造器
	 * 
	 * @param maxSize 栈的大小
	 */
	nodeStact(int maxSize) {
		this.maxSize = maxSize;
		hn = new heroNode[maxSize];
		top = -1;
	}

	/**
	 * 判空
	 */
	public boolean isEmpty() {
		return top == -1;
	}

	/**
	 * 判满
	 */
	public boolean isFull() {
		return top == maxSize - 1;
	}

	/**
	 * 弹出
	 */
	public heroNode pop() {
		if (isEmpty()) {
			System.out.println("栈空");
			return null;
		}
		return hn[top--];
	}

	/**
	 * 压栈
	 */
	public void push(heroNode _hn) {
		if (isFull()) {
			System.out.println("栈满");
		} else {
			hn[++top] = _hn;
		}
	}
}

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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426

二、双向链表

1、双向链表概述

遍历方法和单链表一样，不仅可以向前，也可以向后查找
添加（默认添加到双向链表的最后)
1. 先找到双向链表的最后这个节点
2. temp.next = newHeroNode
3. newHeroNode.pre=temp;
修改：思路和原来的单向链表一样
删除
1. 双向链表可以实现自我删除某个节点
2. 直接找到要州除的这个节点，比如 temp
3. temp.pre.next =temp.next
4. temp.next. pre = temp.pre;

2、代码实现

java

package work.rexhao.linkedlist;

import java.util.Scanner;

public class doubleLinkedListDemo {

	public static void main(String[] args) {
		doubleLinkedList dll = new doubleLinkedList();
		boolean loop = true;
		while (loop) {
			System.out.println("--------");
			System.out.println("1.在尾部添加");
			System.out.println("2.按编号添加");
			System.out.println("3.遍历双向链表");
			System.out.println("4.修改节点");
			System.out.println("5.删除节点");
			System.out.println("6.有效节点个数");
			System.out.println("0.退出");
			System.out.println("--------");
			Scanner sc = new Scanner(System.in);
			int key = sc.nextInt();
			if (key == 1) {
				System.out.println("请输入学生编号：");
				int no = sc.nextInt();
				System.out.println("请输入学生姓名：");
				Scanner sc1 = new Scanner(System.in);
				String name = sc1.nextLine();
				dll.add(new stuNode(no, name));
				System.out.println("添加成功！");
			} else if (key == 2) {
				System.out.println("请输入学生编号：");
				int no = sc.nextInt();
				System.out.println("请输入学生姓名：");
				Scanner sc1 = new Scanner(System.in);
				String name = sc1.nextLine();
				dll.addByNo(new stuNode(no, name));
				System.out.println("添加成功！");
			} else if (key == 3) {
				dll.show();
			} else if (key == 4) {
				System.out.println("请输入学生编号：");
				int no = sc.nextInt();
				System.out.println("请输入学生新的姓名：");
				Scanner sc1 = new Scanner(System.in);
				String name = sc1.nextLine();
				dll.change(new stuNode(no, name));
			} else if (key == 5) {
				System.out.println("请输入学生编号：");
				int no = sc.nextInt();
				dll.delete(no);
			} else if (key == 6) {
				System.out.println("有效节点个数：" + dll.usedNode());
			} else if (key == 0) {
				loop = false;
			} else {
				System.out.println("输入有误！");
			}
		}
	}

}

/**
 * 双向链表
 */
class doubleLinkedList {
	private stuNode head = new stuNode(0, "wmh");

	/**
	 * 有效节点数
	 */
	public int usedNode() {
		int ans = 0;
		stuNode temp = head.next;
		while (temp != null) {
			ans++;
			temp = temp.next;
		}
		return ans;
	}

	/**
	 * 插入
	 */
	public void add(stuNode sn) {
		if (head.next == null) {
			head.next = sn;
			sn.pre = head;
			return;
		}
		stuNode temp = head.next;
		while (true) {
			if (temp.next == null) {
				break;
			}
			temp = temp.next;
		}
		temp.next = sn;
		sn.pre = temp;

	}

	/**
	 * 遍历
	 */
	public void show() {
		if (head.next == null) {
			System.out.println("单链表为空");
			return;
		}
		stuNode temp = head.next;
		while (temp != null) {
			System.out.println(temp);
			temp = temp.next;
		}
	}

	/**
	 * 修改
	 */
	public void change(stuNode sn) {
		if (head.next == null) {
			System.out.println("单链表为空");
			return;
		}
		stuNode temp = head.next;
		while (temp != null) {
			if (temp.getNo() == sn.getNo()) {
				temp.setName(sn.getName());
				temp.setNo(sn.getNo());
				return;
			}
			temp = temp.next;
		}
		System.out.printf("未找到no=%d的节点\n", sn.getNo());
	}

	/**
	 * 自我删除
	 */
	public void delete(int no) {
		if (head.next == null) {
			System.out.println("链表为空");
			return;
		}
		stuNode temp = head.next;
		while (temp != null) {
			if (temp.getNo() == no) {
				/*
				 * 找到了
				 */
				temp.pre.next = temp.next;
				if (temp.next != null) {
					temp.next.pre = temp.pre;
				}
				return;
			}
			temp = temp.next;
		}
		System.out.printf("未找到no=%d的节点\n", no);
	}

	/**
	 * 按照编号添加
	 */
	public void addByNo(stuNode sn) {
		/*
		 * 判空
		 */
		if (head.next == null) {
			head.next = sn;
			sn.pre = head;
			return;
		}
		/*
		 * 判同
		 */
		stuNode temp = head.next;
		while (temp != null) {
			if (temp.getNo() == sn.getNo()) {
				System.out.println("编号相同");
				return;
			}
			temp = temp.next;
		}
		/*
		 * 找位置添加——第一个位置
		 */
		if (sn.getNo() < head.next.getNo()) {
			sn.next = head.next;
			head.next = sn;
			sn.pre = head;
			sn.next.pre = sn;
			return;
		}
		/*
		 * 找位置添加——不是第一个位置
		 */
		temp = head.next;
		while (temp != null) {
			if (temp.next == null) {
				temp.next = sn;
				sn.pre = temp;
				return;
			}
			if (temp.getNo() < sn.getNo() && temp.next.getNo() > sn.getNo()) {
				sn.next = temp.next;
				temp.next = sn;
				sn.pre = head;
				sn.next.pre = sn;
				return;
			}
			temp = temp.next;
		}
	}
}

/**
 * 定义stuNode节点
 */
class stuNode {
	private int no;
	private String name;
	public stuNode next;
	public stuNode pre;

	/**
	 * 构造器
	 * 
	 * @param no   编号
	 * @param name 姓名
	 */
	stuNode(int no, String name) {
		this.name = name;
		this.no = no;
	}

	public int getNo() {
		return no;
	}

	/**
	 * 重写toString
	 */
	@Override
	public String toString() {
		return "[no=" + no + ", name=" + name + "]";
		// 使用双向链表，不能打印next和pre
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}
}

三、单项循环链表与Josepfu问题

1、约瑟夫环概述

设编号为1,2,⋯n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

2、解决思想

用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有口个结点的单循环链表，然后由k结点起从1 开始计数，计到 m 时，对应结点从链表中州除，然后再从被删除结点的下一个结点又从1 开始计数，到最后一个结点从链表中删除算法结束。

3、代码实现

java

package work.rexhao.linkedlist;

import java.util.Scanner;

public class JosepfuDemo {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("总人数:");
		int n = sc.nextInt();
		System.out.print("报号数:");
		int k = sc.nextInt();
		Josepfu(n, k);
	}

	/**
	 * Josepfu问题
	 * 
	 * @param n 人数
	 * @param k 报号数
	 */
	public static void Josepfu(int n, int k) {
		circleSingleLinkedList csll = new circleSingleLinkedList();
		for(int i = 1; i <= n; i++) {
			csll.add(new Node(i));
		}
		Node temp = csll.head;
		int j = 1;
		while(csll.usedNode() != 1) {
			if(j == k) {
				csll.delete(temp.getNum());
				j = 1;
				temp = temp.next;
				continue;
			}
			j++;
			temp = temp.next;
		}
		csll.show();
	}
}

class circleSingleLinkedList {
	public Node head = null;

	/**
	 * 添加节点
	 */
	public void add(Node n) {
		/*
		 * 空链表，直接放后面
		 */
		if (head == null) {
			head = n;
			n.next = head;
			return;
		}
		/*
		 * 非空，遍历加在后面
		 */
		Node temp = head;
		while (temp.next != head) {
			temp = temp.next;
		}
		temp.next = n;
		n.next = head;

	}

	/**
	 * 遍历
	 */
	public void show() {
		Node temp = head;
		boolean loop = true;
		while (loop) {
			System.out.println(temp);
			temp = temp.next;
			if (temp == head) {
				loop = false;
			}
		}
	}

	/**
	 * 有效元素
	 */
	public int usedNode() {
		if (head == null) {
			return 0;
		}
		if (head.next == head) {
			return 1;
		}
		Node temp = head;
		int ans = 1;
		while (temp.next != head) {
			temp = temp.next;
			ans++;
		}
		return ans;
	}

	/**
	 * 删除节点
	 */
	public void delete(int num) {
		/*
		 * 判空
		 */
		if (head == null) {
			System.out.println("链表为空");
			return;
		}
		/*
		 * 删除head节点
		 */
		if (head.getNum() == num) {
			if (head.next == head) {
				/*
				 * 只有一个head
				 */
				head = null;
			} else {
				/*
				 * 还有其他节点
				 */
				// 1.改最后的next
				Node temp = head;
				while (true) {
					if (temp.next == head) {
						temp.next = head.next;
						break;
					}
					temp = temp.next;
				}
				// 2.改head
				head = head.next;
			}
			return;
		}
		/*
		 * 删除其他的节点
		 */

		Node temp = head.next;
		while (true) {
			if (temp.next.getNum() == num) {
				temp.next = temp.next.next;
				return;
			}
			temp = temp.next;
		}
	}
}

class Node {
	private int num;
	public Node next;

	Node(int num, Node next) {
		this.num = num;
		this.next = next;
	}

	Node(int num) {
		this.num = num;
		this.next = null;
	}

	@Override
	public String toString() {
		return "Node[num=" + num + "]";
	}

	public int getNum() {
		return num;
	}

	public void setNum(int num) {
		this.num = num;
	}

}

链表 ​

一、单链表 ​

1、单链表概述 ​

2、面试题 ​

1）有效节点个数 ​

2）倒数第K个节点数据 ​

3）反向遍历——迭代 ​

4）反向遍历——栈 ​

5）合并单链表 ​

3、代码实现 ​

二、双向链表 ​

1、双向链表概述 ​

2、代码实现 ​

三、单项循环链表与Josepfu问题 ​

1、约瑟夫环概述 ​

2、解决思想 ​

3、代码实现 ​

链表

一、单链表

1、单链表概述

2、面试题

1）有效节点个数

2）倒数第K个节点数据

3）反向遍历——迭代

4）反向遍历——栈

5）合并单链表

3、代码实现

二、双向链表

1、双向链表概述

2、代码实现

三、单项循环链表与Josepfu问题

1、约瑟夫环概述

2、解决思想

3、代码实现