一、链表的基本性质
1.1 定义链表结构体
定义链表的结构体是必要的。虽然不定义的话，也会调用默认的构造函数，但这个默认构造函数无法赋初值。理由稍后解释，先来看结构体定义
struct ListNode{
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
定义了结构体后，如果我想定义新的节点，那么赋初值就很方便，如下所示：
ListNode* head = new ListNode(5);
使用默认构造函数初始化节点：
ListNode* head = new ListNode();
head->val = 5;
所以可以看出，如果不定义构造函数使用默认构造函数的话，在初始化的时候就不能直接给变量赋值！
1.2 添加节点
1.3 删除节点
- 若想将A->B->C链表中的B节点删去，只要将A节点的next指针 指向C节点就可以了。那B节点不是依然存留在内存里么？只不过是没有在这个链表里而已。 答案是肯定的，所以在C++里最好是再手动释放这个D节点，释放这块内存。
- 其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。
二、反转链表——绝对高频考题
2.1 题目描述
给定一个单链表的头节点head，请你反转这个链表并返回它。
2.2.1 解题思路1——递归
代码如下
ListNode* reverseList(ListNode* head)
{
if(!head || !head->next)
{
return head;
}
ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newhead;
}
算法时间复杂度：O(n),其中n是链表长度；空间复杂度：O(n)。空间复杂度主要取决于递归所调用的栈空间，最多为n层。
2.2.2 解题思路2——迭代
假设链表为1-2-3-nullptr，我们需要把它反转为nullptr-3-2-1.遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储它的前一个节点。在更改引用之前，还需要存储后一个节点，最后返回新的头引用。
-
先把前节点置空，把head赋给当前节点；
-
然后next = prev，prev = curr， curr = next
-
最后返回previous即可。
代码如下
ListNode* reverseList(ListNode* head)
{
ListNode* prev = nullptr;
ListNode* curr = head;
while(curr)
{
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
算法时间复杂度：O(n),其中n是链表长度；空间复杂度：O(1)。
三、合并两个有序链表
- 将两个有序链表合并为一个新的升序链表并返回。
3.1.1 解题思路1——递归
*
代码如下
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
if(!l1) {
return l2;
}
else if(!l2) {
return l1;
}
else if(l1->val < l2->val) {
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else {
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
时间复杂度为O(m + n),空间复杂度也为O(m + n).
3.1.2 解题思路2——
代码如下
四、删除链表中value为某一值的全部节点
4.1.1 解题思路1——直接删！
代码如下：
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;
}
4.1.2 解题思路2——虚拟头节点法
代码如下：
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while (cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
head = dummyHead->next;
delete dummyHead;
return head;
}
五、两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。请注意，不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
解题思路
- 建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
代码如下
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
六、LC第2题——两链表反向相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。注：本题可以假设除了数字 0 之外，这两个数都不会以 0开头。
解题思路
代码如下：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
int sum;
while(l1 || l2 || sum) {
if(l1) sum += l1->val, l1 = l1->next;
if(l2) sum += l2->val, l2 = l2->next;
curr->next = new ListNode(sum % 10);
curr = curr->next;
sum = sum / 10;
}
return dummy->next;
}
