链表理论基础
- 链表分为 单链表 ，双链表，循坏链表。
- 链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
- 链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
203.移除链表元素
题目链接: 203. 移除链表元素 - 力扣（LeetCode）
题目
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1 输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7 输出：[]
思路
在该题中只需要让节点next指针直接指向下下一个节点就可以了。
但要注意，如果移除的是头结点时该如何操作？
可以考虑两种方法
- 直接使用原来的链表来进行删除操作
- 设置置一个虚拟头结点在进行删除操作
代码
采用虚拟头节点的方式
时间复杂度O(1)
空间复杂度O(n)
1 class Solution {
2 public ListNode removeElements(ListNode head, int val) {
3 if (head == null) {
4 return head;
5 }
6 // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
7 ListNode dummy = new ListNode(-1, head);
8 ListNode pre = dummy; // 进行操作的节点
9 ListNode cur = head; // 当前访问的节点
10 while (cur != null) {
11 if (cur.val == val) {
12 pre.next = cur.next; //让节点next指针直接指向下下一个节点，
13 } else {
14 pre = cur; // 更新需要操作的节点
15 }
16 cur = cur.next; // 更新当前节点
17 }
18 return dummy.next;
19 }
20 }
不添加虚拟节点的方式
时间复杂度O(1)
空间复杂度O(n)
1 class Solution {
2 public ListNode removeElements(ListNode head, int val) {
3 //确保头结点的val != val
4 //当第一个节点等于 val 时，此时由于没有虚拟节点，无法移除第一个节点
5 //所以在前面要先确定第一个节点不等于val
6 while(head != null && head.val == val){
7 head = head.next;
8 }
9
10 if(head == null){
11 return head;
12 }
13 //不添加虚拟节点
14 ListNode pre = head;
15 //确定头结点不为val
16 ListNode cur = head.next;
17 while(cur != null){
18 if(cur.val == val){
19 pre.next = cur.next;
20 }else{
21 pre = cur;
22 }
23 cur = cur.next;
24 }
25 return head;
26 }
27 }
不使用 虚拟节点 和 pre 节点 的方式
1 public ListNode removeElements(ListNode head, int val) {
2 while(head!=null && head.val==val){
3 head = head.next;
4 }
5 ListNode curr = head;
6 while(curr!=null){
7 while(curr.next!=null && curr.next.val == val){
8 curr.next = curr.next.next;
9 }
10 curr = curr.next;
11 }
12 return head;
13 }
707.设计链表
题目链接: 707. 设计链表 - 力扣（LeetCode）
题目
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
示例：
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1-> 3 linkedList.get(1); //返回3
思路
本题目考察对链表的常见操作。
设计一个 虚拟头节点 较容易解决。
代码
单链表
1 //单链表
2 class ListNode {
3 int val;
4 ListNode next;
5 ListNode(){}
6 ListNode(int val) {
7 this.val=val;
8 }
9 ListNode(int val,ListNode next) {
10 this.val=val;
11 this.next = next;
12 }
13 }
14 class MyLinkedList {
15 //size存储链表元素的个数
16 int size;
17 //虚拟头结点
18 ListNode head;
19
20 //初始化链表
21 public MyLinkedList() {
22 size = 0;
23 head = new ListNode(0);
24 }
25
26 //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
27 public int get(int index) {
28 //如果index非法，返回-1
29 if (index < 0 || index >= size) {
30 return -1;
31 }
32 ListNode currentNode = head;
33 //包含一个虚拟头节点，所以查找第 index+1 个节点
34 for (int i = 0; i <= index; i++) {
35 currentNode = currentNode.next;
36 }
37 return currentNode.val;
38 }
39
40 //在链表最前面插入一个节点，等价于在第0个元素前添加
41 public void addAtHead(int val) {
42 addAtIndex(0, val);
43 }
44
45 //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
46 public void addAtTail(int val) {
47 addAtIndex(size, val);
48 }
49
50 // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
51 // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
52 // 如果 index 大于链表的长度，则返回空
53 public void addAtIndex(int index, int val) {
54 if (index > size) {
55 return;
56 }
57 if (index < 0) {
58 index = 0;
59 }
60
61 size++;
62
63 //找到要插入节点的前驱
64 ListNode pred = head;
65 for (int i = 0; i < index; i++) {
66 pred = pred.next;
67 }
68 //插入节点
69 ListNode toAdd = new ListNode(val);
70 toAdd.next = pred.next;
71 pred.next = toAdd;
72 }
73
74 //删除第index个节点
75 public void deleteAtIndex(int index) {
76 if (index < 0 || index >= size) {
77 return;
78 }
79 size--;
80 if (index == 0) {
81 head = head.next;
82 return;
83 }
84 ListNode pred = head;
85 for (int i = 0; i < index ; i++) {
86 pred = pred.next;
87 }
88 //删除节点
89 pred.next = pred.next.next;
90 }
91 }
92
93
94 /**
95 * Your MyLinkedList object will be instantiated and called as such:
96 * MyLinkedList obj = new MyLinkedList();
97 * int param_1 = obj.get(index);
98 * obj.addAtHead(val);
99 * obj.addAtTail(val);
100 * obj.addAtIndex(index,val);
101 * obj.deleteAtIndex(index);
102 */
双链表
206.反转链表
题目链接: 206. 反转链表 - 力扣（LeetCode）
题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
思路
改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。
方法：双指针法 和 递归法。
代码
双指针法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next; // 保存下一个节点
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
标签：head,ListNode,val,随想录,next,链表,移除,节点 From： https://www.cnblogs.com/xpp3/p/17092473.html