算法day03-链表篇（1）
今日任务目录[*]链表理论基础
[*]203.移除链表元素
[*]707.设计链表
[*]206.反转链表
今天这一节是和链表的基础操作相关的，更加复杂的题目我们放到后面由浅入深来做。
一、链表理论基础
二、移除链表元素
这是力扣203题（），本题最关键是要理解虚拟头节点的使用技巧，这对链表题目很重要。
主要思路：对于ACM模式，我们要先构建节点。我们可以从head来遍历这条链表，遇到节点值等于val的节点则删除。那么删除节点的操作怎么做呢?
1) 普通方法对于头节点删除和中间节点的删除操作不一样，头节点只需将指针往下移一个，指向下一个节点，但是中间节点需要指向下下个。
2）添加一个虚拟头节点。这样整个删除的代码都是以同一的逻辑来删除。
1 /** 方法一：
2* Definition for singly-linked list.
3* public class ListNode {
4* int val;
5* ListNode next;
6* ListNode() {}
7* ListNode(int val) { this.val = val; }
8* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9* }
10*/
11 class Solution {
12 public ListNode removeElements(ListNode head, int val) {
13 while(head != null && head.val == val){ //持续的过程
14 head = head.next;
15 }
16 ListNode cur = head;
17 while(cur != null && cur.next != null){ //因为我们要操作cur.next
18 if(cur.next.val == val){ //我们要删除的是cur.next，因为这样能找到它的前一个节点cur
19 cur.next = cur.next.next;
20 }else{
21 cur = cur.next;
22 }
23 }
24 return head;
25 }
26 }<br>//时间复杂度：O（n）<br>//空间复杂度：O（1） 1 class Solution {
2 public ListNode removeElements(ListNode head, int val) {
3 ListNode dummyHead = new ListNode(); //构建虚拟节点指向头节点
4 dummyHead.next = head;
5
6 ListNode cur = dummyHead;
7 while(cur.next != null){
8 if(cur.next.val == val){
9 cur.next = cur.next.next;
10 }else{
11 cur = cur.next;
12 }
13 }
14 return dummyHead.next;
15 }
16 }
三、设计链表
这是力扣707题（707. 设计链表 - 力扣（LeetCode））。这里涉及到链表的一些基本操作，需要仔细弄懂。
1 class MyLinkedList {
2
3 // 定义链表节点内部类
4 class ListNode {
5 int val; // 节点值
6 ListNode next;// 指向下一个节点的指针
7
8 ListNode(int val) {
9 this.val = val;
10 }
11 }
12
13 private int size; // 当前链表元素数量
14 private ListNode dummyHead; // 虚拟头节点（不存储真实数据，只是为了统一操作）
15
16 // 初始化链表
17 public MyLinkedList() {
18 this.size = 0;
19 this.dummyHead = new ListNode(0); // 虚拟头节点值可以随意设，比如0
20 }
21
22 // 获取链表第 index 个节点的值（0-based）
23 public int get(int index) {
24 // 如果索引非法，返回 -1
25 if (index < 0 || index >= size) {
26 return -1;
27 }
28 // 从 dummyHead 后的第一个节点开始走
29 ListNode cur = dummyHead.next;
30 while (index > 0) {
31 cur = cur.next;
32 index--;
33 }
34 return cur.val;
35 }
36
37 // 在链表头部添加一个节点
38 public void addAtHead(int val) {
39 ListNode newNode = new ListNode(val);
40 newNode.next = dummyHead.next;
41 dummyHead.next = newNode;
42 size++;
43 }
44
45 // 在链表尾部添加一个节点
46 public void addAtTail(int val) {
47 ListNode newNode = new ListNode(val);
48 ListNode cur = dummyHead;
49 // 找到最后一个节点
50 while (cur.next != null) {
51 cur = cur.next;
52 }
53 cur.next = newNode;
54 size++;
55 }
56
57 // 在链表指定位置 index 前插入一个节点
58 public void addAtIndex(int index, int val) {
59 // 如果 index > size，无法插入
60 if (index > size) {
61 return;
62 }
63 // 如果 index 小于0，按照在头部插入处理
64 if (index < 0) {
65 index = 0;
66 }
67
68 ListNode newNode = new ListNode(val);
69 ListNode cur = dummyHead;
70 // 找到第 index 个节点的前一个节点
71 while (index > 0) {
72 cur = cur.next;
73 index--;
74 }
75 newNode.next = cur.next;
76 cur.next = newNode;
77 size++;
78 }
79
80 // 删除链表中第 index 个节点
81 public void deleteAtIndex(int index) {
82 // 索引非法，直接返回
83 if (index < 0 || index >= size) {
84 return;
85 }
86 ListNode cur = dummyHead;
87 // 找到要删除节点的前一个节点
88 while (index > 0) {
89 cur = cur.next;
90 index--;
91 }
92 // 删除操作：让前一个节点跳过要删除的节点
93 cur.next = cur.next.next;
94 size--;
95 }
96 } 【相关题目】
[*]LRU
四、反转链表
这是力扣206题（206. 反转链表 - 力扣（LeetCode）），这里有很多反转链表需要注意的点。
1 /**
2* Definition for singly-linked list.
3* public class ListNode {
4* int val;
5* ListNode next;
6* ListNode() {}
7* ListNode(int val) { this.val = val; }
8* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9* }
10*/
11 class Solution {
12 public ListNode reverseList(ListNode head) {
13 ListNode cur = head, pre = null;
14 while(cur != null){ //尾节点的next为null
15 ListNode nxt = cur.next;
16 cur.next = pre;
17 pre = cur;
18 cur = nxt;
19 }
20 return pre;
21 }
22 }<br>//时间复杂度：O(N)，遍历了每个节点<br>//空间复杂度：O(1)，只用了常量级指针【相关题目】
[*]k个一组反转链表
[*]
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]