链表算法题目

1.两数相加

两个非空链表，分别表示两个整数，只不过是反着存储的，即先存储低位在存储高位。要求计算这两个链表所表示数的和，然后再以相同的表示方式将结果表示出来。如示例一：两个数分别是342和465，和为807，但是我们要逆序存储，所以结果链表就是708.

解法：模拟

我们只需要用两个指针同时遍历两个链表，取出相加，相加的值刚好作为新链表的头。再遍历下一个节点的时候，只需要将结果尾插到新链表后即可。

但因为每一个节点只能存储个位数，所以我们在储存时要对相加的结果进行取模，而且两数相加还有可能遇到进位的情况，所以我们还要保存进位，因为进位是在下一位相加时才有用，所以要注意取模和求进位的先后顺序。

我们会遇到那些位数不同的数字相加，要注意循环的结束条件，只有一个为空时，我们仍需要继续遍历，空的那个只需要让其默认是0即可，这样也不会引起问题。当然，当计算到最后一位时，仍有可能进位，但是两个链表都空了，此时直接返回的话，就会出错。所以我们也要保证进位不为0

时间复杂度：O(max(n1,n2))，只需要遍历一遍链表,n1,n2分别是两个链表的长度

空间复杂度：O(1),我们申请了一个哨兵位的头节点，但是再最后释放掉了

// C++/*** 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) {ListNode* newhead = new ListNode;// 哨兵头节点ListNode* tail = newhead; // 尾节点// 遍历链表指针ListNode* cur1 = l1;ListNode* cur2 = l2;int carry = 0;// 如果两个链表还有一个没有走完还得继续走// 如果链表都走完了，但是要记得检查进位，判断是否还有剩余进位while(cur1 || cur2 || carry){// 获取节点的值，如果节点为空则默认该节点的值为0，不影响加的结果carry += cur1 ? cur1->val : 0;carry += cur2 ? cur2->val : 0;// carry的个位就是该节点要存储的，不要忘了保存进位ListNode* newnode = new ListNode(carry % 10);carry /= 10;// 尾插tail->next = newnode;tail = newnode;// 移动cur1/2到下一个节点cur1 = cur1 ? cur1->next : cur1 = nullptr;cur2 = cur2 ? cur2->next : cur2 = nullptr;}// newhead是new出来的，避免内存泄露，在返回之前将其delete掉tail = newhead->next;delete newhead;return tail;}
};

2.链表相加2

这道题与上面很像，这不过这里的链表是按照高位到地位，返回的结果也是按照高位到地位。

解法：

先将两个链表逆置，然后再利用上一题的方法进行相加并得出逆序的结果，最后再将和链表逆置就可以得出答案。

时间复杂度：O(n)

空间复杂度：O(1)

class Solution 
{
public:ListNode* addInList(ListNode* head1, ListNode* head2) {if((head1 == nullptr && head2 == nullptr) || (head1 == nullptr && head2)) return head2;if(head1 && head2 == nullptr) return head1;// 1.先将原链表进行逆置 // 头插法ListNode* newhead1 = new ListNode(0);ListNode* newhead2 = new ListNode(0);while(head1 || head2){if(head1){ListNode* next = head1->next;head1->next = newhead1->next;newhead1->next = head1;head1 = next;}if(head2){ListNode* next = head2->next;head2->next = newhead2->next;newhead2->next = head2;head2 = next;}}// 2.同时遍历两个逆置链表，进行加法运算ListNode* ret = new ListNode(0);ListNode* cur1 = newhead1->next;ListNode* cur2 = newhead2->next;int carry = 0;while(cur1 || cur2 || carry){carry += cur1?cur1->val:0;carry += cur2?cur2->val:0;ListNode* newNode = new ListNode(carry%10);carry /= 10;// 头插法，将和链表逆置回来newNode->next = ret->next;ret->next = newNode;cur1 = cur1?cur1->next:nullptr;cur2 = cur2?cur2->next:nullptr;}cur1 = ret->next;delete ret;delete newhead1;delete newhead2;return cur1;}
};

3.反转链表

解法1：头插法

我们定义一个哨兵头节点，然后遍历原链表，将原链表的节点都头插到哨兵头节点的后面。

时间复杂度：O(n)

空间复杂度：O(1)

ListNode* _ReverseList(ListNode* head)
{// 头插法反转链表if (!head || !head->next) return head;ListNode* ret = new ListNode(0);while (head){ListNode* next = head->next;head->next = ret->next;ret->next = head;head = next;}head = ret->next;delete ret;return head;
}

解法2：双指针：

借助两个指针cur1和cur2，在原链表上修改指针的指向来实现逆置。cur2指向头节点，cur1指向空，然后用cur2遍历原链表，遍历的同时，让cur2的next指向cur1，实现逆置，然后让cur1走到cur2的位置，然后cur2走到下一个位置。在这个过程中需要用一个next指针提前记录cur2的next位置。

时间复杂度：O(n)

空间复杂度：O(1)

ListNode* __ReverseList(ListNode* head)
{// 双指针反转链表if (!head || !head->next) return head;ListNode* cur1 = nullptr;ListNode* cur2 = head;while (cur2){ListNode* next = cur2->next;cur2->next = cur1;cur1 = cur2;cur2 = next;}return cur1;
}

解法3：递归

首先借助递归找到尾节点，以该节点为头节点开始返回。返回的过程中，将该层的head的next的next指针指向自己即head的前一个节点的next指针指向自己，此时就达到了后一个指向前一个，接着将head的next指针指向空，避免成环。接着继续递归返回。

下面是链表递归到尾节点第一次返回的时候：

等到下一层时，head就到了2节点，此时再让前一个节点的next指向自己，在将自己的next置为空，就将2号节点连接到了ans链表中。

时间复杂度：O(n)

空间复杂度：O(n)，递归会消耗栈空间，递归所需的栈空间就是链表的长度

ListNode* ReverseList(ListNode* head)
{// 递归反转链表if (!head || !head->next) return head;ListNode* ans = ReverseList(head->next);head->next->next = head;head->next = nullptr;return ans;
}

4.两两交换链表中的节点

解法1：哨兵头节点+快慢指针

利用快慢双指针遍历原链表，让fast指针先尾插到哨兵头节点后，接着尾插slow，重复该过程。在遍历的过程中，如果原链表是奇数个，最后一次slow不为空，fast为空，退出循环，直接将slow尾插即可；如果原链表是偶数个，最后一个slow和fast都不为空，尾插结束后，slow走到空，循环结束。但记得最后让待返回的链表的尾节点指向空，否则答案可能会错误！

时间复杂度：O(n)，只遍历了一遍链表

空间复杂度：O(1)

 // 借助哨兵头节点+快慢指针ListNode* swapPairs(ListNode* head) {// 链表为空/链表只有一个节点，直接返回if(head == nullptr || head->next == nullptr) return head;// 创建虚拟头节点ListNode* virtualHead = new ListNode;ListNode* tail = virtualHead;// 定义快慢指针ListNode* slow = head;ListNode* fast = slow->next;while(fast && slow){ListNode* _fast = fast;ListNode* _slow = slow;slow = fast->next;if(slow)fast = slow->next;tail->next = _fast;tail = _fast;tail->next = _slow;tail = _slow;} if(slow){tail->next = slow;tail = slow;}tail->next = nullptr;tail = virtualHead->next;delete virtualHead;return tail;}

解法2：哨兵头节点+原地修改链表指向

首先将哨兵头节点连接到原链表头部，接着定义4个指针prev,cur,next,nnext，从哨兵开始依次指向一个节点。接下来只需要根据图示修改指针指向即可：

prev->next = next; next->next = cur;cur->next = nnext;

修改一次之后，cur直接指向第3个节点——nnext，其他的三个指针分别修改好，继续修改指向。在修改next和nnext指针时要注意空指针解引用的问题。

结束条件：当cur遍历到空时，说明已经没有节点需要交换了；当next指向空时，说明只剩cur一个节点了，此时也不需要交换。

时间复杂度：O(n)，每个节点都被访问一次

空间复杂度：O(1)

 ListNode* swapPairs(ListNode* head) {// 链表为空/链表只有一个节点，直接返回if(head == nullptr || head->next == nullptr) return head;// 创建虚拟头节点ListNode* virtualHead = new ListNode;virtualHead->next = head;ListNode* prev = virtualHead;ListNode* cur = head;ListNode* next = cur->next;ListNode* nnext = next->next;while(cur && next){prev->next = next;next->next = cur;cur->next = nnext;prev = cur;cur = nnext;if(cur) next = cur->next;if(next) nnext = next->next;}cur = virtualHead->next;delete virtualHead;return cur;}

解法3：递归

我们将节点两个两个分组，并且我们确保在交换前两个节点时，后面的链表已经交换完成了，并且返回了一个新的头节点tmp。我们用新头节点newhead指向旧头节点oldhead,然后用oldhead指向后面已经完成交换的链表，将两个部分连接起来，其实newhead就是我们完成交换之后的头节点。

简单来说，对于原链表来说，每两个一组的节点，第一个节点是新链表的第二个节点，第二个节点是新链表的头节点。

时间复杂度：O(n)，每一个节点都被访问了

空间复杂度：O(n)，递归所需要的栈空间，每两个节点需要一个函数栈帧

// 递归
ListNode* swapPairs(ListNode* head)
{if (head == nullptr || head->next == nullptr) return head;ListNode* newhead = head->next;ListNode* tmp = swapPairs(newhead->next); // 下层传上来的交换后的头节点newhead->next = head;head->next = tmp;return newhead;
}

5.重排链表

该题的意思其实是按照第一个倒数第一个，第二个倒数第二个...的方式将链表重新排列后返回。

解法：

我们观察规律可以得出，重排后的链表其实是可以由两个链表合并得来的。而且这两个链表就是从原链表中间分开，前半部分和后半部分的逆置。

所以我们的解决策略就是先找出原链表的中心节点，接着将后半部分逆置，然后借助哨兵头节点，将这样个链表进行合并，合并时先尾插前半部分，再尾插后半部分。

1.对于寻找链表的中间节点，我们可以采取快慢双指针的方式，fast一次走两步，slow一次走一步，当fast走到空/尾时，slow的位置就是中间节点的位置。但是这种方法对于奇数链表来说，slow会停在中间位置，对于偶数链表，slow会停在中间靠右的节点。

2.接下来的逆置我们既可以直接逆置slow及以后的部分，也可以逆置slow后面的部分。两者都是可以的。下面只给出偶数节点的例子，对于奇数节点个数也是成立的。

虽然两种方式都可以，但是这里建议将slow之后的链表进行逆置。因为这样可以将原链表断开，形成两个独立的链表，合并时更好处理。如果逆置slow及之后的话，无法将前后链表断开。

3. 采取逆置slow之后，我们会得到两个独立的链表，接下来只需要合并即可。注意合并顺序：先前再后。

时间复杂度：O(n)，虽然三次遍历链表，但整体上依旧是O(n)

空间复杂度：O(1)

void reorderList(ListNode* head)
{// 当链表为空/一个节点/两个节点，都不需要发生变换，直接返回if (head == nullptr || head->next == nullptr || head->next->next == nullptr)return;// 1.找到链表的中间节点，采用快慢双指针// 奇数个slow会落在中间节点// 偶数个slow会落在中间靠右的节点ListNode* fast = head;ListNode* slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}// 2.逆序后半部分链表——头插法// 这里采取逆序mid后面的部分，不包括mid节点ListNode* newhead = new ListNode;ListNode* mid = slow->next; // 先记录下需要逆序的部分slow->next = nullptr; // 将前半部分和需要逆序的部分断开while (mid){ListNode* next = mid->next;mid->next = newhead->next;newhead->next = mid;mid = next;}// 3.合并两个链表-head和newheadListNode* ret = new ListNode;ListNode* tail = ret;ListNode* cur1 = head, * cur2 = newhead->next;while (cur1){tail->next = cur1;tail = cur1;cur1 = cur1->next;if (cur2){tail->next = cur2;tail = cur2;cur2 = cur2->next;}}head = ret->next;delete newhead;delete ret;
}

6.合并K个升序链表

lists的每一个元素都是一个链表，我们需要将这样链表以升序的格式全部合并最终返回。

解法1：两两合并

虽然有多个链表，但是我们可以两个两个合并，用合并的结果在于下一个合并，重复该过程，直到将所有的链表都合并了。

时间复杂度：O(nk^2)，我们假设平均每个链表的节点数是n，有k个链表，第一个链表需要合并k-1次，第二个链表合并k-2次，最后一个链表合并1次。所以加起来就是n*k^2次。

空间复杂度：O(1)

// 1.两两合并
ListNode* _mergeKLists(vector<ListNode*>& lists)
{if (lists.size() == 0) return nullptr;else if (lists.size() == 1) return lists[0];ListNode* ret = lists[0];for (int i = 1; i < lists.size(); ++i){ListNode* tmp = new ListNode;ListNode* tail = tmp;ListNode* cur = lists[i];// 合并两个有序链表while (ret && cur){if (ret && cur && ret->val <= cur->val){tail->next = ret;tail = ret;ret = ret->next;}else if(ret && cur && ret->val > cur->val){tail->next = cur;tail = cur;cur = cur->next;}}while (ret){tail->next = ret;tail = ret;ret = ret->next;}while (cur){tail->next = cur;tail = cur;cur = cur->next;}// 此时cur和ret的和在tmp中，将tmp的值赋给ret// cur与第一次的和继续合并ret = tmp->next;delete tmp;}return ret;
}

解法2：优先级队列——小根堆

我们可以定义k个指针指向每个链表的头，让这k个节点进入小堆，此时堆顶数据就是最小的，我们将他尾插到ret链表，接着删除堆顶数据，将堆顶元素所在链表的下一个节点push到堆中。重复该过程。

时间复杂度：O(nlogk)，每一个节点插入到堆中是logk，因为要进行向下调整

空间复杂度：O(k)，优先级队列中同时最多包含K个节点

// 2.借助priority_queue
ListNode* __mergeKLists(vector<ListNode*>& lists)
{// 借助小根堆，先将vector中的所有头节点放入堆中，此时堆顶节点的val值就是最小的。// 取出堆顶节点尾插到哨兵位头节点后，接着从堆中删除该节点，将该节点的next插入到堆中。// 堆不为空，持续该过程。// 再将节点插入到堆中时要判断该节点是否为空size_t n = lists.size();if (n == 0) return nullptr;else if (n == 1) return lists[0];ListNode* ret = new ListNode;ListNode* tail = ret;priority_queue < ListNode*, vector<ListNode*>, decltype([](ListNode* l1, ListNode* l2) {return l1->val > l2->val; }) > heap;for (auto l : lists)if (l) heap.emplace(l);while (!heap.empty()){ListNode* min = heap.top();heap.pop();tail->next = min;tail = min;if (min->next)heap.emplace(min->next);}tail = ret->next;delete ret;return tail;
}

解法三：分治——归并策略

我们可以采取归并排序的策略，将所有的链表分为两部分，先合并左边，在合并右边，最后将这两个合并好的链表再一合并即可。

时间复杂度：O(nklogk)，划分的过程中高度是logk，一共有nk个节点

空间复杂度：O(logk)，递归的深度是logk，消耗了logk的栈空间

// 3. 分治——归并策略ListNode* mergeTwoList(ListNode* cur1, ListNode* cur2){if(!(cur1) || !(cur2)) return !cur1 ? cur2 : cur1;ListNode ret(0);ListNode* tail = &ret;while(cur1 && cur2){if(cur1->val <= cur2->val){tail->next = cur1;tail = cur1;cur1 = cur1->next;}else{tail->next = cur2;tail = cur2;cur2 = cur2->next;}}tail->next = cur1?cur1:cur2;return ret.next;}ListNode* merge(vector<ListNode*>& lists, int left, int right){if(left>=right) return left == right ? lists[left] : nullptr;int mid = (right-left)/2+left;// [left, mid] [mid+1, right]ListNode* cur1 = merge(lists, left, mid); // 接收左边合并后的结果ListNode* cur2 = merge(lists, mid+1, right); // 接收右边合并后的结果return mergeTwoList(cur1, cur2); // 合并两个有序数组}ListNode* mergeKLists(vector<ListNode*>& lists){  return merge(lists,0,lists.size()-1);}

7.K个一组反转链表

给一个节点，在一个数k，将链表每k个为一组，进行反转，如果最后不足k个，就直接保留。

解法：模拟

1.我们可以首先求出需要反转多少次，n个节点，k个一组，那么就有n/k组，每组都要反转一次，一共反转n/k次。

2.头插法反转链表，需要注意，每进行一次反转要标记第一个头插到链表的节点，下一次反转将节点都插在标记节点的后面，而不是哨兵头结点的后面。

时间复杂度：O(n)

空间复杂度：O(1)

ListNode* reverseKGroup(ListNode* head, int k)
{if (!head || k == 1) return head;// 1.先算出需要进行几次逆序操作int n = 0;ListNode* cur = head;while (cur){n += 1;cur = cur->next;}n /= k;// 2.n次逆序ListNode* newhead = new ListNode;ListNode* tail = newhead;cur = head;while (n--){ListNode* tmp = tail;for (int i = 0; i < k; ++i){if (i == 0) tail = cur; // 标记每次反转的第一个节点ListNode* next = cur->next;cur->next = tmp->next;tmp->next = cur;cur = next;}}if (cur) tail->next = cur;tail = newhead->next;delete newhead;return tail;
}