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);
}
};