删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例 ：
输入：head = [4,5,1,9], node = 5提示：
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
- 链表至少包含两个节点。
- 链表中所有节点的值都是唯一的。
- 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
- 不要从你的函数中返回任何结果。
#pragma once
#include<iostream>
//Definition for singly-linked list.
struct ListNode { //单链表
int val; //值
ListNode* next; //指向下一个node的地址
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
void deleteNode(ListNode* node) {
//（狸猫换***，巧妙）
node->val = node->next->val; //用下一个node的值覆盖该node的值
node->next = node->next->next; //再把下一个node删除
}
};
//题意是要删除指定node，但是我们无法访问链表的head，所以要在无法访问head的条件下删除node（这里用一招狸猫换***，用下一个node值来覆盖这个node,再把下一个node删除，从而达到相同的目的）
删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？
示例 ：
输入：head = [1,2,3,4,5], n = 2输出：[1,2,3,5]
提示：
示例 ：
- 链表中结点的数目为 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
#pragma once
#include<stack>
//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) {
/*by myself(暴力，计算链表长度长度)
ListNode* dummy = new ListNode(0, head); //head表示头节点(也是第一个有效节点)，因为这里要删除一个节点，大多数情况是删除指定节点后返回head，但要考虑链表长度为1的情况，如果删除唯一的head后，就不能返回head了，应该返回nullptr（所以这里的处理方法是，在head前面插入一个dummy节点，删除节点后返回dummy.next。如果链表长度len>1则返回的是head，len==1则返回的是nullptr）
ListNode* i = dummy;
int count = 0; //count统计链表的长度
while (i->next != nullptr) { //获取链表长度
count++;
i = i->next;
}
int m = count - n; //m表示从dummy节点开始要往后移动的次数，最终i指向的节点是 指定删除节点 的前一个节点
i = dummy;
while (m) {
i = i->next;
m--;
}
i->next = i->next->next; //删除指定节点
ListNode* result = dummy->next;
delete dummy; //注：上面手动new了一个dummy，所有要手动delete回收
return result; //返回dummy节点的下一个节点指针。如果len==1，则表示nullptr，len>1等价于head
*/
/*(栈)
ListNode* dummy = new ListNode(0, head); //同上，定义一个dummy且dummy.next指向head。dummy在操作链表中特别重要!
ListNode* i = dummy;
std::stack<ListNode*> stk;
while (i!= nullptr) { //将链表所有节点全部入栈，包括dummy节点
stk.push(i);
i = i->next;
}
for (int j = 0; j < n; j++) { //利用栈的特性。将最后n个节点(也就是是栈顶前n个节点)出栈
stk.pop();
}
ListNode* prev = stk.top(); //此时栈顶为 需要删除的指定节点 的前一个节点
prev->next = prev->next->next; //删除指定节点
ListNode* result = dummy->next;
delete dummy; //手动释放dummy
return result; //返回dummy节点的下一个节点指针
*/
//(双指针)
ListNode* dummy = new ListNode(0, head); //同上
ListNode* first = dummy; //定义前后指针，且初始化为dummy
ListNode* last = dummy;
while (first->next != nullptr) { //后指针指向最后一个node时结束循环
if (n != 0) { //首先保持first指针不动，向后移动last指针，拉开first和last指针距离为n
first = first->next;
n--;
}
else { //保持first和last指针距离为n，同时向后移动。循环结束时，last指针指向最后一个节点，first指针指向 需要删除的指定节点 的前一个节点
last = last->next;
first= first->next;
}
}
last->next = last->next->next; //删除节点
ListNode* result = dummy->next;
delete dummy; //手动释法dummy
return result; //返回dummy节点的下一个节点指针
}
};
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。示例 ：
输入：head = [1,2,3,4,5]输出：[5,4,3,2,1]
输入：head = []输出：[]
提示：
相关标签：递归 链表
示例 ：
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
相关标签：递归 链表
#pragma once
#include<stack>
//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) {
/*by myself(栈)
if (head==nullptr) { //判断是不是空链表
return head;
}
std::stack<ListNode*>stk; //定义一个栈来存储节点指针
ListNode* cur = head;
while (cur != nullptr) { //所有节点入栈
stk.push(cur);
cur = cur->next;
}
ListNode* result = stk.top(); //首先获取最后一个节点(也就是反转链表之后的头节点)，之后要返回的，所以先保存下来
cur = stk.top();
stk.pop(); //获取一个节点之后记得弹出该节点
while (!stk.empty()) { //反转链表
cur->next = stk.top();
cur = stk.top();
stk.pop();
}
cur->next = nullptr; //最后一个节点不要忘记将其next设置为nullptr;
return result; //返回反转链表后的head(也就是反转之前的最后一个节点)
*/
/*by myself(三指针)
if (head == nullptr || head->next == nullptr) { //链表为空，或者len=1返回head
return head;
}
ListNode* first = head; //头指针
ListNode* last = head->next; //尾指针
ListNode* next = last->next; //尾指针指向节点的下一个节点指针（目的是为了在last->next = first之后，保存原来的last->next，从而继续遍历原来的链表）
first->next = nullptr; //首先设置头指针next=nullptr(也是反转后的尾指针)
while (next != nullptr) { //prev指针遍历整个链表
last->next = first; //反转
first = last; //反转之后，三个指针同时向后移动
last = next;
next = next->next;
}
last->next = first; //因为循环结束时，最后一个节点还未反转，所以这里补上
return last; //返回源链表的最后一个节点(也是反转后链表的头节点)
*/
/*(迭代)
ListNode* prev = nullptr; //前一个节点指针
ListNode* cur = head; //当前节点指针
while (cur!=nullptr) { //遍历整个链表
ListNode* next = cur->next; //下一个节点指针(目的是为了在last->next = first之后，保存原来的last->next，从而继续遍历原来的链表)
cur->next = prev;
prev = cur; //向后移动prev和next指针
cur = next;
}
return prev; //返回prev指针，即反转后链表的head（循环结束时，prev指向反转前链表的最后一个节点，cur为这个节点的next，即nullptr）
*/
//(递归,妙！）
if (head==nullptr||head->next == nullptr) { //两种情况返回，第一种就是空链表的情况，第二种就是head节点为原链表最后一个节点（也就是递归的最后一层"子链表"长度为1时）
return head;
}
//(错误)
//ListNode* last = reverseList(head->next); //这里只是反着链回去，但最终返回的是 反转后的链表 的尾节点(即原链表的head)，而不是 反转后链表 的头节点(即原链表的尾节点)
//last->next = head;
//head->next = nullptr;
//return head; //这里返回的是反转后链表的尾节点，作为返回上一层的last
ListNode* h = reverseList(head->next);//每一层并没有用到h，而是仅仅获取原链表最后一个节点，不断返回到最高层。
head->next->next = head; //这里的head表示 当前递归层的"子链表"的head，仅仅利用 "每一层的head"和递归的特性 来进行反转。（对于第5层来说，直接返回h5；对于第4层来说，这条语句可以看成 (head4->next)->next = head4 也就是h5->next=head4；对于第3层来说，可以看成(head3->next)->next = head3 也就是head4->next=head3；对于第2层来说，可以看成(head2->next)->next = head2 也就是head3->next=head2；对于第1层来说，可以看成(head1->next)->next = head1 也就是head2->next=head1；
head->next = nullptr;
return h; //里返回的节点h一直没有变,一直都是最后一次递归返回的值(即原链表的最后一个节点，也就是反转后链表的头节点)
}
};
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 ：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []输出：[]
输入：l1 = [], l2 = [0]输出：[0]
提示：
示例 1:
- 两个链表的节点数目范围是 [0, 50]
- -100 <= Node.val <= 100
- l1 和 l2 均按 非递减顺序 排列
#pragma once
//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) {
/*by myself(不带dummy节点版本的暴力解法)
ListNode* prev = nullptr; //这里选择以链表l1作为被插入链表，初始化prev节点指针为nullptr,cur1节点指针为l1(prev为cur1指针指向节点的前一个节点指针)
ListNode* cur1 = l1;
ListNode* cur2 = l2;
ListNode* result = l1; //result作为合并链表后链表的head返回
if (l1 == nullptr) { //如过l1链表(被插入链表)为空，直接返回l2
return l2;
}
while (cur1 != nullptr && cur2 != nullptr) { //遍历比较并合并俩个链表，无论那个链表遍历结束则结束循环
if (cur2->val >= cur1->val) { //如果l2对应节点val大于l1对应节点val,则向后移动l1链表中的prev和cur1指针
prev = cur1;
cur1 = cur1->next;
}
else { //否则，在cur1之前，prev之后插入cur2指向的节点
ListNode* t = cur2; //这里先保存cur2指针到t，之后将cur2向后移动
cur2 = cur2->next;
if (cur1 == l1) { //注：如果cur1==l1时，即在 l1指向节点 之前插入cur2（因为此时的prev为nullptr！所以要特别处理）
t->next = cur1; //先将t->next指向cur1
if (prev != nullptr) { //注：这里又要考虑一个特殊情况，即连续在 l1指向节点 之前插入多个节点（因为在 l1指向节点 之前插入一个节点后，prev=t，但是再次插入节点输入中间插入，prev此时指向有效节点，则必须prev->next=t）
prev->next = t;
}
prev = t;
result = l2; //因为这里在 l1指向节点 插入l2节点，所以合并后的链表head应该为l2
}
else { //如果cur1!=l1则说明不是头部插入，而是中间插入，则插入t，并且移动prev（prev应该紧贴在cur1之前）
prev->next = t;
t->next = cur1;
prev = t;
}
}
}
if ( cur1 == nullptr) { //如果cur1(即被插入链表)遍历完，则说明l2链表还有一部分链表未合并完。因为是有序链表，所以直接在 prev指向节点(也是l1的尾节点) 后链接上l2链表余下部分
prev->next = cur2;
}
return result; //返回合并链表后的head
*/
/*(带dummy节点的暴力解法)
ListNode* dummy = new ListNode(0, l1); //先定义一个dummy节点，插入到l1链表(即被插入链表)前面
ListNode* prev = dummy;
ListNode* cur1 = l1;
ListNode* cur2 = l2;
while (cur1 != nullptr && cur2!= nullptr) { //遍历比较并合并俩个链表，无论那个链表遍历结束则结束循环
if (cur1->val < cur2->val) { //如果l2对应节点val大于l1对应节点val,则向后移动l1链表中的prev和cur1指针
prev = cur1;
cur1 = cur1->next;
}
else { //否则，在prv之后cur1之前插入cur2节点
ListNode* t = cur2; //因为要继续移动cur2节点指针遍历链表，所以要将cur2节点指针保存到t，再将cur2向后移动
cur2 = cur2->next;
prev->next = t; //插入cur2节点，并且向后移动prev（保证prev紧跟cur1,而且只有在 cur1->val < cur2->val 条件下移动cur1）
t->next = cur1;
prev = t;
}
}
if (cur1 == nullptr) { //如果cur1(即被插入链表)遍历完，则说明l2链表还有一部分链表未合并完。因为是有序链表，所以直接在 prev指向节点(也是l1的尾节点) 后链接上l2链表余下部分
prev->next = cur2;
}
ListNode* result = dummy->next; //使用dummy节点可以省去考虑在l1头部之前插入(此时prev指向无效节点)，和l1头部之前连续插入的特殊情况，并且返回合并节点head即dummy->next。但是注意：记得手动释法dummy，所以先保留dummy->next，再释法dummy。
delete dummy; //手动释法dummy
return result; //返回合并后链表的head(即dummy->next)
*/
/*(递归，无dummy结点)
if (l1 == nullptr) {
return l2; //l1==nullptr说名链表遍历完，l2的链表还有未遍历到的部分，剩余子链表head就是l2,直接返回l2，将插入到合并后的链表后面
}
else
if (l2 == nullptr) { //同上
return l1;
}
else
if (l1->val >= l2->val) { //如果对应结点(即该递归层的子链表head)l1->val>=l2->val，则取出该子链表l2的head(即l2结点指针),继续调用merge(l1,l2->next)。这里说明该层俩条子链表中 l2节点指针 指向的结点是最小值，继续递归比较除该结点外的l1子链表和l2子链表，进入下一层，返回的结果就是作为该层去掉来 l2节点指针 的next（该返回的 结点指针指向的结点 也是下一层的最小值，从而达到结点从小到大有序的被链接，只不过是从尾往头）
l2->next = mergeTwoLists(l1, l2->next);
return l2; //在该递归层合并的子链表的head就是被拿下的结点l2,所以返回该结点指针
}
else {
l1->next = mergeTwoLists(l1->next, l2); //同理，都是保留最小那个结点，剩下链表继续进行合并
return l1;
}
//l1: 1,4,5
//l2: 1, 2, 3, 6
//1->1->2->3->4->5->6
//merge(1, 1) : l1.next = 1, return l1(1)
//merge(4, 1) : l2.next = 2, return l2(1)
//merge(4, 2) : l2.next = 3, return l2(2)
//merge(4, 3) : l2, next = 4, return l2(3)
//merge(4, 6) : l1.next = 5, return l1(4)
//merge(5, 6) : l1.next = 6, return l1(5)
//merge(null, 6) : return l2(6)
*/
//(迭代，有dummy结点)
ListNode* dummy = new ListNode(0); //先定义一个dummy节点（定义dummy结点最大好处就是保存头节点，即head=dummy->next。其次可以忽略边界问题(因为每次插入都相当于在俩个结点中间插入，特别方便)）
ListNode* prev = dummy; //prev结点指针指向每次迭代合并后的"子链表"的尾结点，并且每次迭代都是在prev后插入结点
ListNode* cur1 = l1; //cur1，cur2指向未合并的"子链表"l1,l2的头结点（本题有三条链表，prev所在的合并过程的"子链表"，l1所在剩余未合并的"l1子链表"，l2所在剩余未合并的"l2子链表"）
ListNode* cur2 = l2;
while (cur1 != nullptr && cur2 != nullptr) { //遍历比较并合并俩个链表，无论那个链表遍历结束则结束循环
if (cur1->val <= cur2->val) { //如果cur1->val <= cur2->val，表示cur1指向结点应该被合并，所以插入到prev后面，并且prev向后移动再次指向尾部结点(即新合并进来的结点cur1),同时cur1向后移动指向其所在的"l1子链表"的下一个结点
prev->next = cur1;
prev = cur1;
cur1 = cur1->next;
}
else { //同理
prev->next = cur2;
prev = cur2;
cur2 = cur2->next;
}
}
if (cur1 == nullptr) { //如果循环结束，cur1==nullptr，表示海剩余"l2子链表"未合并。理解知道，此时直接将其链接到prev后即可(即prev->next = cur2)
prev->next = cur2;
}
else { //相反，同理
prev->next = cur1;
}
ListNode* result = dummy->next; //先保存，再手动是否dummy结点
delete dummy;
return result; //返回合并后链表的head(即dummy->next)
}
}; 回文链表
请判断一个链表是否为回文链表。示例 1:
输入: 1->2输出: false
输入: 1->2->2->1输出: true
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
相关标签：栈 递归 链表 双指针
相关标签：栈 递归 链表 双指针
#pragma once
//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* reverse_list(ListNode* head);
bool recursivelyCheck(ListNode* cur);
ListNode* frontpointer;
bool isPalindrome(ListNode* head) {
/*(反转后半部分链表)
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) { //通过快慢指针找到链表的中间结点(fast每次向后移动俩个结点，slow向后移动一个结点)，fast==nullptr时结束循环容易理解(fast->next==nullptr时也要结束循环，因为fast每次向后移动俩个结点，没有该条件在链表len为奇数时会导致非法引用,因为fast会跳过nullptr)
fast = fast->next->next;
slow = slow->next;
}
if (fast != nullptr) { //fast!=nullptr,说明是因为fast->next==nullptr而跳出循环，说明链表len为奇数，所以slow此时指向中间结点，应该反转中间结点之后的链表，所以slow=slow->next
slow = slow->next;
}
ListNode* first = head;
ListNode* last = reverse_list(slow);
while (last != nullptr) { //将对称后半部分链表反转后，对俩部分链表进行遍历逐个比较
if (first->val != last->val) {
return false;
}
first = first->next;
last = last->next;
}
return true;
*/
//by myself(递归)
frontpointer = head; //注：frontpointer应该是一个全局遍历
return recursivelyCheck(head);
}
};
bool Solution::recursivelyCheck(ListNode* cur) { //利用递归判断是否是回文
if (cur == nullptr) { //表示遍历结束这里返回true
return true;
}
if(!recursivelyCheck(cur->next)) { //如果下一递归层向上返回false,说明cur->val != frontpointer->val，判断结束，所以一直向上返回false
return false;
}
if (cur->val != frontpointer->val) { //如果不满足该条件说明不是回文，则返回false
return false;
}
frontpointer = frontpointer->next; //程序执行到这里，说明该递归层判断条件，所以forntpointer向后移动指向下一个结点
return true; //返回上一层继续比较
}
ListNode* Solution::reverse_list(ListNode* head) { //反转链表(迭代)
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur!=nullptr) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
环形链表
给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
如果链表中存在环，则返回 true 。 否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0输出：true解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1输出：false解释：链表中没有环。
提示：
- 链表中节点的数目范围是 [0, 104]
- -105 <= Node.val <= 105
- pos 为 -1 或者链表中的一个 有效索引 。
#pragma once
#include<unordered_set>
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode* head) {
/*by myself(暴力解法，带dummy版本)
ListNode* dummy = new ListNode(0); //定义一个dummy，并且插入链表前面
dummy->next = head;
ListNode* prev = dummy; //定义一个cur，prev指向cur之前的结点
ListNode* cur = head;
while (cur != nullptr) { //遍历链表，对应每一个cur，都与其之前所有结点指针进行比较，出现重复即有环
ListNode* i = dummy;
while (i != prev) { //注：因为要找出cur之前与cur相对的结点指针，所有不能用i!=cur。(这里用i!=prev，且加上prev与cur的比较来代替)
if (i == cur || prev == cur) { //prev==cur，既是弥补当没有循环时，prev与cur的比较；也是补充当cur结点自循环的这种特殊情况
return true;
}
i = i->next;
}
prev = cur;
cur = cur->next;
}
delete dummy;
return false;
*/
/*by myself(暴力解法，不带dummy结点)
ListNode* prev = head;
ListNode* cur = head;
if (head != nullptr && head == head->next) { //不带dummy结点就要单独排除 当链表只有一个结点，且其next指向自身 的情况
return true;
}
while (cur != nullptr) {
ListNode* i = head;
while (i != prev) {
if (i == cur || prev == cur) {
return true;
}
i = i->next;
}
prev = cur;
cur = cur->next;
}
return false;
*/
/*by myself(hash解法)
std::unordered_set<ListNode*>hash; //创建一个hash表，用来存储前面没有出现环时的结点指针
ListNode* cur = head;
while (cur != nullptr) {
if (hash.find(cur)!=hash.end()) { //hash.find(cur)!=hash.end()说明在hash表中找到与cur相同的结点指针，即出现环
return true;
}
hash.insert(cur); //否则继续将cur插入，且cur指向下一个新结点，继续遍历查找
cur = cur->next;
}
return false;
*/
//(快慢指针)
ListNode* fast = head;
ListNode* slow = head;
while (fast != nullptr && fast->next != nullptr) { //fast == nullptr表示全部遍历完毕结束循环；fast->next != nullptr是防止链表只有一个结点且不成环的情况下fast会引起非法操作(因为fast每次向后移动俩个结点)
fast = fast->next->next; //fast指针每次向后移动两个结点，slow每次向后移动一个结点
slow = slow->next;
if(slow == fast) { //如果slow==fast，说明肯定成环，此时fast正好超slow一圈，而不是slow赶上fast
return true;
}
}
return false;
}
};
京公网安备 11010502036488号