链表
链表
21.合并两个有序链表
题目： 将两个升序链表合并为一个新的升序链表并返回。
思路：
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
1.定义一个初始头节点dummy，存放合并链表
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
ListNode* p1 = list1;
ListNode* p2 = list2;
2.比较两个链表的节点大小，把小的放在p之后
while(p1 != nullptr && p2 != nullptr) {
if (p1->val > p2->val) {
p->next = p2;
p2 = p2->next;
} else {
p->next = p1;
p1 = p1->next;
}
p = p->next;
}
3.剩下的谁的链表不为空，把它的所有值都接在p之后。
if (p1 != nullptr) {
p->next = p1;
}
if (p2 != nullptr) {
p->next = p2;
}
return dummy->next;
}
- 定义一个初始头节点dummy，存放合并链表。
- 比较两个链表p1，p2的节点大小，把小的放在p之后。
- 最后将剩余的不为空的链表p1或p2全放在p后面。
86.分隔链表
题目： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
思路：
ListNode* partition(ListNode* head, int x) {
1.创建两个虚拟头节点dummy1，dummy2，分别存放小于和大于x的链表。
ListNode* dummy1 = new ListNode(-1);
ListNode* dummy2 = new ListNode(-1);
ListNode* p1 = dummy1;
ListNode* p2 = dummy2;
ListNode* p = head;
2.将链表所指值与x比较，将节点放入对应位置
while(p != nullptr) {
if (p->val < x) {
p1->next = p;
p1 = p1->next;
} else {
p2->next = p;
p2 = p2->next;
}
[! 3.当赋值结束后，p = p->next, 但需要断开原节点的next指针，避免之后两个链表指向同一个节点]
ListNode* temp = p->next;
p->next = nullptr;
p = temp;
}
4. 最后将小链表与大链表连接起来
p1->next = dummy2->next;
return dummy1->next;
}
- 创建两个虚拟头节点dummy1，dummy2，分别存放小于和大于x的链表。
- 将链表所指值与x比较，将节点放入对应位置。
- 当赋值结束后，p = p->next, 但需要断开原节点的next指针，避免之后两个链表之间存在多余的错误指向。
- 最后将小链表与大链表连接起来
23.合并 k 个有序链表
题目： 给你一个链表数组，每个链表都已经按升序排列。将所有链表合并到一个升序链表中，返回合并后的链表。
思路： 采用优先队列（时间复杂度o(N logN)）
1.首先重写比较函数（小根堆），构建优先队列。
struct compare {
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
ListNode* mergeKLists(Vector<ListNode*>& lists) {
2.创建一个虚拟头节点。
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
3.将三个链表的头节点添加到优先级序列中。
for (auto node: lists) {
if (node) {
pq.push(node);
}
}
4.每次取一个最小的值放在p之后，再将对应链表的下一个节点添加进来（优先级队列里保持只有3个元素）
while (!pq.empty()) {
ListNode* temp = pq.top();
p->next = temp;
p = p->next;
5.将对应链表的下一个节点添加进来。
if (temp->next) {
pq.push(temp.next);
}
}
return dummy->next;
}
- 首先重写比较函数（小根堆），构建优先队列。
- 创建一个虚拟头节点，存放结果。
- 将三个链表的头节点添加到优先级序列中。
- 每次取一个最小的值放在p之后，再将对应链表的下一个节点添加进来（优先级队列里保持只有3个元素）。
- 将对应链表的下一个节点添加进来。
19.删除链表的倒数第 N 个结点
题目： 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
思路： 双指针法（p1先走n步，再p1，p2同步走）
ListNode* removeNthFromEnd(ListNode* head, int n) {
1.定义虚拟头节点。
ListNode* dummy = new ListNode(-1);
dummy->next = head;
2.定义双指针。
ListNode* p1 = dummy;
ListNode* p2 = dummy;
3.先让p1指针走n步。
for (int i = 0; i < n; i++) {
p1 = p1->next;
}
4.接着p1，p2一起走。最后p1指向最后一个元素，p2指向倒数n+1个元素。
while (p1->next != nullptr) {
p1 = p1->next;
p2 = p2->next;
}
5.删除节点。
p2->next = p2->next->next;
return dummy->next;
}
- 定义虚拟头节点。
- 定义双指针。
- 先让p1指针走n步。
- 接着p1，p2一起走。最后p1指向最后一个元素，p2指向倒数n+1个元素。
- 删除节点。
876. 链表的中间结点
题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。
思路：双指针法（p1走两步，p2走一步）
ListNode* middleNode(LsitNode* head) {
// 1.定义一个虚拟头节点，指向head。
ListNode* dummy = new ListNode(-1);
dummy->next = head;
// 2.定义双指针，指向dummy。
ListNode* p1 = dummy;
ListNode* p2 = dummy;
// 3.p1指针每移动一位，p2指针移动两位，直到越界。
while (p2->next != nullptr && p2->next->next != nullptr) {
p1 = p1->next;
p2 = p2->next->next;
}
// 4.此时p1恰好指向中间节点的前一位。
return p1->next;
}
- 定义一个虚拟头节点，指向head。
- 定义双指针，指向dummy。
- p1指针每移动一位，p2指针移动两位，直到越界。
- 此时p1恰好指向中间节点的前一位。
141. 环形链表
题目： 给你一个链表的头节点 head ，判断链表中是否有环。
思路： 使用双指针，相遇则有环。
bol hasCycle(ListNode* head) {
// 1.定义一个虚拟头节点，指向head。
ListNode* dummy = new ListNode(-1);
dummy->next = head;
// 2.定义双指针
ListNode p1 = dummy;
ListNode p2 = dummy;
// 3.p1每次走一步，p2每次走两步。
while (p2->next != nullptr && p2->next->nxt != nullptr) {
p1 = p1->next;
p2 = p2->next->next;
// 4.如果p1与p2相遇，则有环。
if (p1 == p2) {
return true;
}
}
return false;
}
- 定义一个虚拟头节点，指向head。
- 定义双指针p1，p2。
- p1每次走一步，p2每次走两步。
- 如果p1与p2相遇，则有环。
142.环形链表Ⅱ
题目： 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
思路： 双指针法，先判断是否有环。如果有环，在相遇点让p1，p2同速前进，再次相遇位置就是环入口。
ListNode* detectCycle(ListNode* head) {
// 1.定义一个虚拟头节点
ListNode* dummy = new ListNode(-1);
dummy->next = head;
// 2.定义双指针
ListNode* p1 = dummy;
ListNode* p2 = dummy;
// 3.如果找到环则从相遇位置退出。
bool isFind = false;
while (p2->next != nullptr && p2->next->next != nullptr) {
p1 = p1->next;
p2 = p2->next;
if (p1 == p2) {
isFind = true;
break;
}
}
// 4.让p1指针回归原点，再次相遇的位置就是环入口。
if (isFind == true) {
p1 = dummy;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
} else {
// 5.找不到环则直接返回null。
return nullptr;
}
}
- 定义一个虚拟头节点。
- 定义双指针。
- 如果找到环则从相遇位置退出。
- 让p1指针回归原点，再次相遇的位置就是环入口。
- 找不到环则直接返回nullptr。
160.相交链表
题目： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
思路： 可采用双指针的方法，指针p1遍历完A后可接着遍历B。而指针p2遍历完B后可接着遍历A。如果有交点，那么肯定在那一点两指针指向的是同一个节点。如果没有相交，那么两指针最后肯定都指向尾端，都等于nullptr。
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
// 1.创建俩虚拟头节点
ListNode* dummy1 = new ListNode(-1);
ListNode* dummy2 = new ListNode(-1);
dummy1->next = headA;
dummy2->next = headB;
// 2.创建双指针
ListNode* p1 = dummy1;
ListNode* p2 = dummy2;
// 3.指针p1遍历完A后可接着遍历B。而指针p2遍历完B后可接着遍历A。
while (p1 != p2) {
if (p1 != nullptr) {
p1 = p1->next;
} else {
p1 = dummy2->next;
}
if (p2 != nullptr) {
p2 = p2->next;
} else {
p2 = dummy1->next;
}
}
// 4.如果有交点，那么两指针指向的是中间的同一个节点。如果没有相交，那么两指针最后肯定都指向尾端为nullptr。
return p1;
}
- 创建俩虚拟头节点。
- 创建双指针。
- 指针p1遍历完A后可接着遍历B。而指针p2遍历完B后可接着遍历A。
- 如果有交点，那么两指针指向的是中间的同一个节点。如果没有相交，那么两指针最后肯定都指向尾端为nullptr。
83.删除排序链表中的重复元素
题目： 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
思路：
- 创建快慢指针p1,p2.
- 快指针依次遍历,慢指针找到非重复节点.
- p2每次遍历，记得切断p1的后续连接。
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
// 1.创建快慢指针p1,p2.
ListNode* p1 = head;
ListNode* p2 = head;
// 2.快指针依次遍历,慢指针找到非重复节点.
while (p2->next != nullptr) {
// 3.p2每次遍历，记得切断p1的后续连接。
p2 = p2->next;
p1->next = nullptr;
if (p2->val > p1->val) {
p1->next = p2;
p1 = p1->next;
}
}
return head;
}