链表
- 链表的定义：链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针）
- 数组是在内存中是连续分布的，但是链表在内存中不是连续分布的
- C++中的链表定义方式：
1 | // 单链表 |
构造函数可以自己定义，也可以不自己定义C++自己默认生成。
如果自己定义构造函数, 则可以直接赋值:1
ListNode* head = new ListNode(5);
如果使用默认的构造函数，不可以直接赋值：
1 | ListNode* head = new ListNode(); |
链表的类型:单链表，双链表，循环链表
链表删除结点:
链表添加结点:
性能分析:
移除链表元素时注意删除时直接将指针指向下一个结点, C++要记得删除该节点占的空间。 为了处理要删除的结点是头节点的情况，有两种方法:一种是直接对头节点特殊处理，如果要删除头节点就将头节点设为下一个节点。另一种是设置一个虚拟头指针dummyhead, 然后对链表进行统一处理。
203. 移除链表元素
方法1:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 删除头结点
while (head != NULL && head->val == val) { // 注意这里不是if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
// 删除非头结点
ListNode* cur = head;
while (cur != NULL && cur->next != NULL) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
};
注意声明cur时要在处理完头结点后, 不能先将head结点复制给cur再对head结点进行操作。
方法2：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode *current = dummyhead;
while(current->next != NULL)
{
if(current->next->val == val)
{
ListNode *temp = current->next;
current->next = current->next->next;
delete temp;
}
else
{
current = current->next;
}
}
head = dummyhead->next;
delete dummyhead;
return head;
}
};
707.设计链表:
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点。
1 | class MyLinkedList { |
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表, 双指针法。
1 | /** |
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
1 | /** |
注意一定要有ListNode* temp2 = current->next->next->next; 否则系统会不知道将current->next->next的下一个结点是什么。
19.删除链表的倒数第 N 个结点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/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *dummynode = new ListNode(0);
dummynode->next = head;
ListNode *fast = dummynode;
ListNode *slow = dummynode;
int m = n + 1;
while(m--)
{
fast = fast->next;
}
while(fast != nullptr)
{
fast = fast->next;
slow = slow->next;
}
ListNode *temp = slow->next;
slow->next = slow->next->next;
delete temp;
return dummynode->next;
}
};
双指针的思想，注意为了处理只有一个结点的情况，需要加入一个dummynode结点，然后删除第n个让fast指针前进n+1个，然后fast和slow一起移动，最后删掉slow->next即可。
面试题 02.07. 链表相交
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
1 | /** |
思路:先比较两个链表的长度，结尾对齐，然后移动指针知道找到两个相同的元素。
142.环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路: 双指针的思想，创建一个快指针和一个慢指针，快指针一次走两个步长，满指针一次走一个步长。如果有环，则两指针一定会橡胶，且快指针比满指针多走了n圈。
x = z + (n - 1) * (y + z), 因此可以再新建两个指针，一个在头结点，一个在相遇结点，同时向后移动，如果两个指针相遇则找到环形入口节点。
1 | /** |