01链表基础操作
# 01 链表基础操作
链表是由节点和指针构成的数据结构，每个节点存有一个值，和一个指向下一个节点的指针，因此很多链表问题可以用递归来处理。不同于数组，链表并不能直接获取任意节点的值，必须要通过指针找到该节点后才能获取其值。同理，在未遍历到链表结尾时，我们也无法知道链表的长度，除非依赖其他数据结构储存长度。链表一般表示方法如下。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 在节点 a->b 中插入 c 插入操作
ListNode *p = a;
c->next = b;
p->next = c;
p = c;
// 从链表 a->c->b 中删除节点 c
ListNode *p = c;
c = c->next;
a->next = c;
delete(p);
// 交换链表 a->c->b->d 中的 c 和 b 节点
a->next = b; // a 指向 b
c->next = b->next; // c 指向 d
b->next = c; // b 指向 c
由于在进行链表操作时，尤其是删除节点时，经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题：
- 一是尽量处理当前节点的下一个节点而非当前节点本身
- 二是建立一个虚拟节点 (dummy node)，使其指向当前链表的头节点，这样即使原链表所有节点全被删除，也会有一个 dummy 存在，返回 dummy->next 即可。
# 206 反转链表 (opens new window)
翻转一个链表。
输入一个链表，输出该链表翻转后的结果。
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
解析：
反转链表需要建立一个指向头节点的虚拟节点 prev，使用头节点的反转操作与其他节点保持一致。另外需要注意的是节点 next 指向改变的顺序，首先需要保存当前节点的 next 指向，然后修改其 next 指向为前一节点，最后移动指向前驱节点和当前节点的指针，完成一次反转操作。重复该操作，直至所有节点完成反转。
/**
* 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* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* next = head;
while(head){
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
};
本题也可以采用递归解决，终止条件为当前节点为空说明链表遍历完成。
/**
* 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* reverseListRec(ListNode* head, ListNode* prev){
if(!head){
return prev;
}
ListNode* next = head->next;
head->next = prev;
return reverseListRec(next,head);
}
ListNode* reverseList(ListNode* head) {
return reverseListRec(head,nullptr);
}
};
# 83 删除排序链表中的重复元素 (opens new window)
给定一个按升序排列的链表，删除其中所有重复的元素
输入一个链表，输出该链表删除重复元素后的结果
输入：head = [1,1,2,3,3] 输出：[1,2,3]
解析：
本题的本质上就是简单的链表删除节点操作，注意回收内存空间。
/**
* 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* deleteDuplicates(ListNode* head) {
if(!head || !head->next){
return head;
}
ListNode *cur = head;
while(cur->next){
if(cur->val == cur->next->val){
ListNode *p = cur->next;
cur->next = p->next;
delete(p);
}else{
cur = cur->next;
}
}
return head;
}
};
# 328 奇偶链表 (opens new window)
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
输入一个链表，输出链表根据节点编号奇偶性重新组织后的结果
输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL
解析：
本题并不复杂，只需要将奇偶编号的节点分开再合并即可。
首先，将第一个节点作为奇数编号链表的头节点，第二个节点作为偶数编号链表的头节点
然后，分别定义两个指针指向奇链表和偶链表的尾部，在原链表中：奇数编号节点的next就是偶数编号的节点，同样偶数编号节点的next就是奇数编号节点。
所以一个奇偶链表的构造操作例子如下：
// 原链表
1 2 3 4
a->b->c->d
// 构造过程
ListNode *odd = a, *even = b; // 将 a 作为奇链表的头节点， b 作为偶链表的头节点，odd指向奇链表尾部，even指向偶链表尾部
odd->next = even->next; // a 指向 c
odd = odd->next; // odd 指向 c
even->next = odd->next; // b 指向 d
even = even->next; // even 指向 d
/**
* 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* oddEvenList(ListNode* head) {
if(!head || !head->next){
return head;
}
ListNode *evenHead = head->next;
ListNode *odd = head, *even = head->next;
while(even && even->next){
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};
# 24 两两交换链表中的节点 (opens new window)
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
输入一个链表，输出该链表交换后的结果。
输入：head = [1,2,3,4] 输出：[2,1,4,3]
解析：
本题的关键就是不要把指针指向搞混，要注意两个相邻节点交换中指针的变换顺序
/**
* 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* swapPairs(ListNode* head) {
ListNode *p = head, *s = nullptr;
if(p && p->next){
s = p->next;
p->next = s->next;
s->next = p;
head = s;
while(p->next&& p->next->next){
s = p->next->next;
p->next->next = s->next;
s->next = p->next;
p->next = s;
p = s->next;
}
}
return head;
}
};
采用递归更好理解本题，用 head 表示原始链表的头节点，新的链表的第二个节点，用 newHead 表示新的链表的头节点，原始链表的第二个节点，则原始链表中的其余节点的头节点是 newHead->next。令 head->next = swapPairs(newHead->next)，表示将其余节点进行两两交换，交换后的新的头节点为 head 的下一个节点。然后令 newHead->next = head，即完成了所有节点的交换。最后返回新的链表的头节点 newHead。
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* newHead = head->next;
head->next = swapPairs(newHead->next);
newHead->next = head;
return newHead;
}
};
# 21 合并两个有序链表 (opens new window)
给定两个增序的链表，试将其合并成一个增序的链表。
输入两个链表，输出一个链表，表示两个链表合并的结果。
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
解析：
本题可以采用双指针求解，首先建立一个虚拟指针 dummy，其next指向合并后链表的头节点。用两个指针分别指向两个链表，逐个比较节点值大小插入合并链表。
/**
* 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1 || !l2){
return l1?l1:l2;
}
ListNode dummy;
ListNode* cur = &dummy;
ListNode* p1 = l1;
ListNode* p2 = l2;
while(p1&&p2){
if(p1->val < p2->val){
cur->next = p1;
p1 = p1->next;
}else{
cur->next = p2;
p2 = p2->next;
}
cur = cur->next;
}
cur->next = p1?p1:p2;
return dummy.next;
}
};
本题也可以采用递归实现，将两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1 || !l2){
return l1?l1:l2;
}
if(l1->val > l2->val){
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
};
本题也可以采用STL中的容器适配器 priority_queue，把两个链表头节点存储在一个优先队列中，每次提取头节点值较小的那个节点，直到两个链表都被提取完为止。
需要注意的是 priority_queue 默认的元素比较方法是less<T>，即默认为最大值元素在前面的最大堆，维持着递减关系。如果我们想要获取最小的节点值，则需要实现一个最小堆，因此比较函数应该维持递增关系。实现侧策略就是使用函数对象 (opens new window)，自定义 priority_queue 的元素比较方法，在该函数对象中重载 operator() ，使用大于号而不是等减关系时的小于号进行比较。
struct myCompare{
bool operator()(ListNode* a, ListNode* b){
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1 || !l2){
return l1?l1:l2;
}
priority_queue<ListNode*, vector<ListNode*>, myCompare> pq;
pq.push(l1);
pq.push(l2);
ListNode dummy;
ListNode* cur = &dummy;
while(!pq.empty()){
cur->next = pq.top();
pq.pop();
cur = cur->next;
if(cur->next){
pq.push(cur->next);
}
}
return dummy.next;
}
};
# 148 排序链表 (opens new window)
给定一个链表，请将其按 升序 排列并返回 排序后的链表
输入一个链表，输出按升序排序的链表
输入：head = [4,2,1,3] 输出：[1,2,3,4]
解析：
本题可以采用归并排序的思想解决。
分治策略：首先使用快慢指针找链表中点的方法找到链表中点，然后以此将链表分割为两个部分，然后再进行递归的划分链表，直到不可划分。在寻找中点需要注意的是不能直接以 nullptr 判断快指针是否达到终点，而是要将其与链表尾节点 tail 进行比较。
分割完成之后，使用合并两个链表的方法，将链表按照升序合并，最终形成完整的升序链表。
/**
* 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* mergeTwoList(ListNode* l1, ListNode* l2){
if(!l1 || !l2) return l1?l1:l2;
ListNode head;
ListNode *tail = &head;
ListNode *p1 = l1, *p2 = l2;
while(p1 && p2){
if(p1->val < p2->val){
tail->next = p1;
p1 = p1->next;
}else{
tail->next = p2;
p2 = p2->next;
}
tail = tail->next;
}
tail->next = p1?p1:p2;
return head.next;
}
ListNode* mergeSort(ListNode* head, ListNode* tail){
if(!head) return head;
if(head->next == tail){
head->next = nullptr;
return head;
}
// 寻找链表中点
ListNode *fast = head, *slow=head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
// 根据链表中点递归分割，并合并结果
return mergeTwoList(mergeSort(head,mid),mergeSort(mid,tail));
}
ListNode* sortList(ListNode* head) {
return mergeSort(head,nullptr);
}
};