-------------------------------------------基础题参照leetcode----------------------------------------------------------------------------------------------------------
【2】两数相加
/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sub1=0,sub2=0,count=0,temp =0;
stack<int> temp_st;
int sum=0;
while(l1){
temp_st.push(l1->val);
l1 = l1->next;
count++;//计数
}
while(count--){
//while的逻辑，先使用count=3，然后再减小，再进来，count直接为2了
sub1+= temp_st.top()*pow(10,count);
temp_st.pop();
}
count =0;
while(l2){
temp_st.push(l2->val);
l2 = l2->next;
count++;//计数
}
while(count--){
sub2+= temp_st.top()*pow(10,count);
temp_st.pop();
}
sum = sub1+sub2;
//头插法
//ListNode* dummy = new ListNode(0);
ListNode* node = new ListNode(sum%10);//定义返回链表头
ListNode* temp_node;
sum /= 10;
while(sum/10){
temp_node = node;
ListNode* node = new ListNode(sum%10);
node->next = temp_node;
}
return node;
}
};
第二题的另外一种做法：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = nullptr,*tail = nullptr;
int carry=0;//两数都不会以0开头
while(l1 ||l2){//除非链表都非空，否则继续执行
int n1 = l1?l1->val:0;//l1非空指向l1->val，否则指向0
int n2 = l2?l2->val:0;
int sum = n1+n2+carry;//先加高位 7 ，再放到最后低位去，则carry为上次低位的进位值
if (!head) {
head = tail = new ListNode(sum % 10);
} else {
tail->next = new ListNode(sum % 10);
tail = tail->next;
}
carry = sum / 10;//carry为进位值
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = new ListNode(carry);//尾插法，需要指定head在前面不动
}
return head;
}
};
！！【148】排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
方法一：转为数组
空间复杂度o(n),时间复杂度o(n)
/**
* 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* sortList(ListNode* head) {
int count =0;
vector<int> temp_vec;
ListNode* tail = nullptr;
ListNode* head2 = nullptr;
while(head){
temp_vec.push_back(head->val);
head= head->next;
count++;
}
sort(temp_vec.begin(),temp_vec.end());
tail = head2 = new ListNode(0);//尾插法
for(int i =0;i<count;i++){
tail->next = new ListNode(temp_vec[i]);
tail = tail->next;
}
return head2->next;
}
};
方法二：归并排序（分治算法）
自底向上归并排序，空间复杂度o(1).
首先先回顾一下递归调用：【21】合并两个有序链表
要明白，①递归函数必须要有终止条件。②递归函数先不断调用自身，直到遇到 终止条件以后进行回溯，最终返回答案。
所以根据【21】题，终止条件：
两个链表为空，表示我们对链表已经合并完成。
如何递归：判断l1和l2哪个头结点更小，然后较小的结点的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* list1, ListNode* list2) {
//终止条件 list1.list2有一个遍历到null就终止条件
if(list1 == NULL)return list2;
if(list2 == NULL)return list1;
//递归条件
if(list1->val<list2->val){
list1->next = mergeTwoLists(list1->next,list2);
return list1;//有返回类型，就要返回
}else{
list2->next = mergeTwoLists(list1,list2->next);
return list2;
}
}
};
但是这里出现了一个问题，就是递归的空间复杂度不是o(1)
递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度 1*n
递归算法的时间复杂度=每次递归的时间复杂度递归次数 12^n
归并排序：此方法时间复杂度 O(nlogn)O(nlogn)O(nlogn)，空间复杂度 O(1)O(1)O(1)。
【138】随机链表的复制
方法1：空间复杂度O(N):哈希表使用线性大小的额外空间。
时间复杂度O(N):两轮遍历链表，使用O(N)时间。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* cur = head;
unordered_map<Node*,Node*> listmp;//当前链表 排序后链表
while(cur != NULL){
listmp[cur] = new Node(cur->val);//能存储丰富的指针信息
cur = cur->next;
}
cur = head;//重新回到链表头
//构建新链表的next和ramdom指向
while(cur != NULL){
listmp[cur]->next = listmp[cur->next];//真的好牛，都不用拿出来操作
listmp[cur]->random = listmp[cur->random];
cur = cur->next;
}
return listmp[head];
}
};
方法二：拼接+拆分
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
//方法2：拼接 拆分链表
//原节点1->新节点1->原节点2->新节点2...拼接链表
if(head == NULL) return NULL;
Node* cur = head;
//复制各个节点，并且构建拼接链表
while(cur!=NULL){
Node* tmp = new Node(cur->val);
tmp->next = cur->next;
cur->next = tmp;
cur = tmp->next;
}
// 2. 构建各新节点的 random 指向
cur = head;
while(cur != nullptr) {
if(cur->random != nullptr)
cur->next->random = cur->random->next;//太牛了，又转回来了
cur = cur->next->next;
}
// 3. 拆分两链表
cur = head->next;
Node* pre = head, *res = head->next;
while(cur->next != nullptr) {
pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr; // 单独处理原链表尾节点
return res; // 返回新链表头节点
}
};
【203】移除链表元素
/**
* 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* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0, head);
ListNode* temp = dummyHead;
while (temp->next) {
if (temp->next->val == val) {
temp->next = temp->next->next;
} else {
temp = temp->next;
}
}
return dummyHead->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* 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;
}
};
【206】反转链表
双指针法
/**
* 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* cur = head;//当前节点指向头结点
ListNode* pre = NULL;//双指针
ListNode* tmp;
while(cur){//如果cur是NULL就出错啦
tmp = cur->next;//存储下一个结点
cur->next = pre;//改变指向
pre = cur;//Pre移动到cur
cur = tmp;//cur移动到cur->next
}
return pre;
}
};
//第二次刷：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if( head == NULL || head->next == NULL )return head;
ListNode* left = NULL;
ListNode* mid = head;
ListNode* right = NULL;
while( mid ){
right = mid->next;//改变指向
mid->next = left;
left = mid;//后移
mid = right;
}
return left;
}
};
时间复杂度o(n),空间复杂度o(1)。
！！【707】设计链表
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3
class MyLinkedList {
public:
struct ListNode{
int val;
ListNode* next;
ListNode(int x):val(x),next(NULL){};
};
MyLinkedList() {//构造函数
dummyhead = new ListNode(0);//初始化
size = 0;//初始化
}
//注意cur到底取dummyhead,还是取dummyhead->next
int get(int index) {//5.获取链表中下标为 index 的节点的值。
if(index<0 || index >size-1){//小标不能小于零 也不能越界
return -1;
}
ListNode* cur = dummyhead->next;//索引是从head：0开始记，dummyhead不参与引用
while(index--){
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {//1.将一个值为 val 的节点插入到链表中第一个元素之前。
ListNode* node= new ListNode(val);//先定义一个新节点存储val值
node->next = dummyhead->next;//先尾部指向
dummyhead->next = node;//后头部被指
size++;//增加了结点
}
void addAtTail(int val) {//2.将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
ListNode* node = new ListNode(val);//定义一个新结点存储val值,结点后指向NULL
ListNode* cur = dummyhead;//不是dummynode->next，防止空链表的情况
while(cur->next!=NULL){//遍历链表，不能用size,会改变size的值
cur = cur->next;//遍历到最后
}
cur->next = node;
size++;
}
//3.将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
//如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。
//如果 index 比长度更大，该节点将 不会插入 到链表中。
void addAtIndex(int index, int val) {
if(index > size)return;//数组下标 0,1.. size是0,1,2...（只有dummyhead，size=0）
if(index<0)return;
ListNode* node = new ListNode(val);//定义新结点存储val
ListNode* cur = dummyhead;//为什么这里和get不一样：cur要在插入结点之前
while(index--){
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
size++;
}
void deleteAtIndex(int index) {//4.
if(index<0 || index >size-1){//小标不能小于零 也不能越界
return;
}
ListNode* cur = dummyhead;
while(index--){
cur = cur->next;
}
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete(tmp);
size--;
}
private:
int size;//定义链表大小
ListNode* dummyhead;//定义虚拟头结点
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
增加打印链表功能，还有就是在ACM模式下验证，捋清楚什么时候是cur = dummyhead->next;
cur = dummyhead->next：当我们int get(int index)时，因为dummyhead没有索引，所以可以直接从head开始设置。
但是在之后 void addAtTail(int val)， void addAtIndex(int index, int val) ，void deleteAtIndex(int index)的情况下，要对链表进行增删操作，需要提前一个结点，所以此时就直接让cur = dummyhead。
【19】删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
要删除倒数第n个结点，需要在倒数第n+1(前一个结点处)进行删除。所以fast和slow指针需要间隔n+1位置。先让fast指针在n+1处，再同时把fast和slow指针向后移，整个操作用到的时间复杂度是o(n),空间复杂度o(1)。
示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
/**
* 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) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* cur = dummyhead;
ListNode* pre = dummyhead;
int size = 0;
while(n-- && cur != NULL){//cur和pre间隔n步
cur = cur->next;
}
cur = cur->next;//cur还要再走一步，删除需要在结点的上一个结点
while(cur!=NULL){
cur = cur->next;
pre = pre->next;
}
//经典的删除结点操作
ListNode* tmp = pre->next;
pre->next = pre->next->next;
delete(tmp);
return dummyhead->next;
}
};
【24】两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
/**
* 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* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* cur = dummyhead;
ListNode* tmp;
ListNode* tmp1;
while(cur->next!=NULL && cur->next->next!=NULL){
tmp = cur->next;
cur->next = cur->next->next;//步骤一
tmp1 = cur->next->next;
cur->next->next = tmp;//步骤二
tmp->next = tmp1;//步骤三
cur = cur->next->next;
}
return dummyhead->next;
}
};
【92】反转链表II
/**
* 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* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummyhead = new ListNode(0);
dummyhead->next = head;
ListNode* tmp;
ListNode* tmp1;
ListNode* leftnode = dummyhead;
ListNode* rightnode = dummyhead;
while(leftnode!= NULL && leftnode->val != left){
tmp = leftnode;//保存的是leftnode的前一个结点
leftnode = leftnode->next;
}
while(rightnode!=NULL && rightnode->val != right){
rightnode= rightnode->next;
}
tmp1 = rightnode->next;//保存rightnode下一个结点
//翻转链表 双指针法
ListNode* tmp2;//第三个结点
ListNode* pre = tmp;//第一个结点
ListNode* cur = leftnode;//第二个结点
while(cur != tmp1){
tmp2 = cur->next;
cur->next = pre;
pre = cur;
cur = tmp2;
}
tmp->next = cur;
leftnode->next = tmp1;
return dummyhead->next;
}
};
【160】相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交**：**
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//快慢指针 要保证链式结构不变就令取变量
ListNode* Aptr = headA;
ListNode* Bptr = headB;
while(Aptr!=Bptr){
Aptr = Aptr == NULL? headA:Aptr->next;//如果没碰到就从头再来，因为速度不一样总会碰上
Bptr = Bptr == NULL? headB:Bptr->next;
}
return Aptr;
}
};
【141】环形链表
给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
进阶：用o(1)常量内存解决此问题。
因为才做了哈希表，所以环形链表的题目我认为可以用哈希表存储每个结点的值，到环形链表时，第一个find的结点值就是环开始的位置。但是这样的内存肯定是很大的。第二种方法是快慢指针，快慢指针在环处必定会相遇，这种内存就不会很大。
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> list_set;//存储结点值
while(head != NULL){
if(list_set.count(head)){//出现过这个元素就返回1
return true;
}else{//没有出现过就存储
list_set.insert(head);
head = head->next;
}
}
return false;//不是环形链表最后指针会指向NULL(要是不在意这个HEAD值的话可以直接看是否是NULL)
}
};
另外一种是快慢指针的方式：
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==NULL||head->next ==NULL)return false;
ListNode* fast = head->next;
ListNode* slow = head;
while(fast!=slow){//当快指针没有追上慢指针的时候
if(fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}else return false;
}
return true;
}
};
【142】环形链表II
同上面一道题，只是需要我们返回进入环形链表的第一个结点。所以我们也可以用哈希表或者快慢指针的方式来做。
**哈希表做的话，由于是无序的，所以第一个被查找的结点就是一个入环的结点。**就很牛逼！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> set;//定义set
while(head!=NULL){
if(set.find(head)!=set.end()){//找到了
return head;
}else{
set.insert(head);
head = head->next;
}
}
return NULL;
}
};
快慢指针相遇的位置不一定是在入环的第一个结点处，所以两个指针相遇以后还要再返回一定的距离去找入环的地方：
忽略fast指针和slow指针两者重复走的圈数，那么slow指针走的步数为：a+b。fast指针走的步数为a+b+n(b+c)。可以在代码里设定fast指针走两步，slow指针每次走一步，那么有fast指针步数 = 2*slow指针步数。则有2x(a+b) =a+b+nx(b+c) —>由于我们求的是入口的结点—>需要a------->a =(n-1)(b+c)+c (n>=1)fast指针至少要比slow指针多走一圈。
当n= 1的时候，a=c,意味着一个指针从头结点出发，从相遇的结点也出发一个指针，这两个指针每次都只走一个结点，那么当这两个指针相遇的时候，就是环形入口的结点。同理n>1,相当于fast在环里面多跑了n圈。 如下图所示：
所以这道题的核心就是在环内的相遇结点处，指派两个指针，一个从head走，一个从当前相遇结点走，他们相遇的地方一定是环的入口结点。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast =head;
ListNode* slow =head;
ListNode* prev1 = head;
ListNode* prev2;
while(fast != NULL && fast->next!=NULL){//两个条件都要满足
fast = fast->next->next;//先移动再判断
slow = slow->next;
if(slow == fast){
prev2 = fast;
while(prev1 != prev2){
prev1 = prev1->next;
prev2 = prev2->next;
}
return prev1;
}
}
return NULL;
}
};
循环链表解决约瑟夫问题：约瑟夫问题 C++求解_c++约瑟夫问题_MilkLeong的博客-CSDN博客
【876】链表的中间结点
给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
步骤：首先遍历整个链表，求出index，再返回
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int index =0;//定义链表下标
ListNode* prev = head;
while(prev!=NULL){
index++;
prev = prev->next;
}
if(index%2 ==0){//偶数
index = index/2;
while(index--){
head = head->next;
}
}
else{//奇数
index = index/2;
while(index--){
head = head->next;
}
}
return head;
}
};
快慢指针：每次快指针比慢指针多走两步，则快指针到链表末尾的时候，慢指针正好在中间的位置。(奇数链表在中间，偶数链表在靠前的中间结点)。
ListNode* endOfFirstHalf(ListNode* head){
ListNode* fast = head;
ListNode* slow = head;
while(fast->next!=NULL && fast->next->next!=NULL){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
【86】分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
/**
* 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* middleNode(ListNode* head) {
int index =0;//定义链表下标
ListNode* prev = head;
while(prev!=NULL){
index++;
prev = prev->next;
}
index = index/2;
while(index--){
head = head->next;
}
return head;
}
};
【21】合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
/**
* 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* list1, ListNode* list2) {
ListNode* dummyhead = new ListNode(-1);//定义虚拟头结点
ListNode* prev = dummyhead;//定义临时结点
while(list1!=NULL && list2!=NULL){
if(list1->val>list2->val){
prev->next = list2;
list2 = list2->next;
}else{
prev->next = list1;
list1 = list1->next;
}
prev = prev->next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
prev->next = list1 == nullptr ? list2 : list1;
dummyhead = dummyhead->next;
return dummyhead;//preHead和 prev公用一个地址
}
};
//递归
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1 == NULL)return list2;
if(list2 == NULL)return list1;
if(list1->val <list2->val){
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
【23】合并K个升序排序
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。(lists中的子集个数是不定的)。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
这道题跟上道题类似，但是合并的链表要比上个的多,相当于上道题是这道题的子集。可知，合并两个有序链表可以使用迭代或者递归来完成。容易想到，对于合并K个链表，可以从头开始两两合并。时间复杂度 O(kn) ，空间复杂度 O(1)
class Solution {
public:
//递归调用
ListNode* merge(ListNode* p1,ListNode* p2){
if(!p1)return p2;
if(!p2)return p1;
if(p1->val<=p2->val){
p1->next = merge(p1->next, p2);
return p1;
}
else{
p2->next = merge(p1, p2->next);
return p2;
}
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(!lists.size())return NULL;
ListNode* head =lists[0];
for(int i =1;i<lists.size();i++){
if(lists[i]){
head = merge(head,lists[i]);
}
}
return head;
}
};
!【234】回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
最开始我想的是，翻转链表然后与原链表进行比较（快慢指针法），但是在测试的过程中发现，始终过不了[1,1,2,1]这个测试案例，然后调试的时候发现这样做是会该变原始的head的（共用地址），翻转以后的reverlist和head已经变了：head是跟cur一起共用地址了。head和cur是共用地址的，所以最后head也要被改变，这样并不能进行比较。
要用快慢指针，正确的做法是，我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该**将链表恢复原样。**虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。
该方法虽然可以将空间复杂度降到o(1),但是在并发环境下，该方法也有缺点，在并发环境下，函数运行的时候需要锁定其他线程或对进程 对 链表的访问，因为函数在执行过程中链表是会被修改的。
整个流程可以分为以下五个步骤：
1.找到前半部分链表的尾结点（找到中间结点）。2.翻转后半部分的链表 3.判断是否回文 4.恢复链表5.返回结果
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode* firstHalfEnd = endOfFirstHalf(head);
ListNode* secondHalfStart = reverseList(firstHalfEnd->next);
// 判断是否回文
ListNode* p1 = head;
ListNode* p2 = secondHalfStart;
bool result = true;
while (result && p2 != nullptr) {
if (p1->val != p2->val) {
result = false;
}
p1 = p1->next;
p2 = p2->next;
}
// 还原链表并返回结果
firstHalfEnd->next = reverseList(secondHalfStart);
return result;
}
ListNode* reverseList(ListNode* head) {//翻转链表
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next;//临时变量存储下一个结点
curr->next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
ListNode* endOfFirstHalf(ListNode* head) {//返回后半截的第一个结点 [1,2,2,1] 则是返回 [2,2,1]
ListNode* fast = head;
ListNode* slow = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
class Solution {
public:
ListNode* reverseList(ListNode* head){//翻转链表
ListNode* cur = head;
ListNode* pre = NULL;
ListNode* tmp;//保存临时结点
while(cur){
tmp = cur->next;//保存cur之后的结点
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;//返回一定是pre，cur已经指向NULL了
}
ListNode* FindMiddleNode(ListNode* head){//找到中间结点
ListNode* midnode = head;
ListNode* tmp = head;
int index =0;
while(midnode && midnode->next){//不要改变head的结构
tmp = tmp->next;
index++;
}
index = index/2;
while(index--){
midnode = midnode->next;
}
return midnode;
}
bool isPalindrome(ListNode* head) {
if(!head)return true;
ListNode* tmphead = head;
ListNode* reverlist;
reverlist = reverseList(FindMiddleNode(tmphead));
while(head != NULL){
if(head->val != reverlist->val){
//tmphead = FindMiddleNode(tmphead);
return false;
}else{
head = head->next;
reverlist = reverlist->next;
}
}
// tmphead = FindMiddleNode(tmphead);
return true;
}
};
【25】 K个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。