链表真的太重要了，本文的行文结构按照链表类题目的两大解法分类：虚拟节点、快慢指针。
1. 虚拟节点
虚拟节点有两个作用：
- 保护head，便于返回
- 用于节点交换的引导
002 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解答：
需要运用加法进位的技术，具体参考数学那一篇中讲解。也需要用到虚拟节点的办法。注意虚拟节点的next
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1==nullptr||l2==nullptr) return nullptr;
ListNode* index=new ListNode(0);
ListNode* pre=index;
int carry=0;
while(l1!=nullptr||l2!=nullptr){
int sum=carry;
carry=0;
if(l1!=nullptr){
sum+=l1->val;
l1=l1->next;
}
if(l2!=nullptr){
sum+=l2->val;
l2=l2->next;
}
if(sum>=10){
carry=sum/10;
sum=sum%10;
}
ListNode* node=new ListNode(sum);
index->next=node;
index=index->next;
}
if(carry!=0){
ListNode* node=new ListNode(carry);
index->next=node;
}
return pre->next;
}
021 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
解答：
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* pre=new ListNode(0);
ListNode* cur=pre;
while(l1&&l2)
{
if(l1->val<l2->val)
{
cur->next=l1;
cur=cur->next;
l1=l1->next;
}
else
{
cur->next=l2;
cur=cur->next;
l2=l2->next;
}
}
if(l1!=nullptr) cur->next=l1;
if(l2!=nullptr) cur->next=l2;
return pre->next;
}
024 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
给定 1->2->3->4, 你应该返回 2->1->4->3.
解答：
注意，不能返回head，否则会变为1-4-3，应该先预设一个dummy来准备返回。
必须first&&first->next，针对上线的单数的情况。
ListNode* swapPairs(ListNode* head) {
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* first = head;
ListNode* dummy = pre;
while(first&&first->next)
{
ListNode* last = first->next;
first->next=last->next;
last->next=first;
pre->next=last;
pre=first;
first=first->next;
}
return dummy->next;
}
083 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2->3->3
输出: 1->2->3
解答：
ListNode* deleteDuplicates(ListNode* head) {
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* cur=head;
while(cur)
{
ListNode* last=cur->next;
while(last!=nullptr&&cur->val==last->val)
{
last=last->next;
}
cur->next=last;
cur=cur->next;
}
return pre->next;
}
082 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
输入: 1->2->3->3->4->4->5
输出: 1->2->5
解答：
时刻要牢记three&&two->next->val==three->val，用之前要先判断是否为null！
ListNode* deleteDuplicates(ListNode* head) {
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* one=pre;
while(one->next&&one->next->next)
{
ListNode* two = one->next;
ListNode* three = one->next->next;
while(three&&two->val==three->val)
{
three=three->next;
}
if(three&&two->next->val==three->val)//没有重复
one=one->next;
else
one->next=three;
}
return pre->next;
}
86 分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
解答：
ListNode* partition(ListNode* head, int x) {
ListNode dummyHead1 = new ListNode(0);
ListNode dummyHead2 = new ListNode(0);
ListNode node1 = dummyHead1;
ListNode node2 = dummyHead2;
while(head){
if(head->val<x){
node1->next=head;
node1=node1->next;
head=head->next;
}else{
node2->next=head;
node2=node2->next;
head=head->next;
}
}
node2->next=NULL; //防止自环
node1->next=dummyHead2.next;
return dummyHead1.next;
}
206 反转链表
反转一个单链表。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解答：
ListNode* reverseList(ListNode* head) {
if(!head) return nullptr;
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* cur=head;
while(cur->next)
{
ListNode* last = cur->next;
cur->next=last->next;
last->next=pre->next;
pre->next=last;
}
return pre->next;
}
092 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解答：
pre一定要随动，所以需要一个dummy来返回
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(!head) return nullptr;
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* dummy=pre;
ListNode* cur=head;
int flag=n-m;
while(m!=1)
{
cur=cur->next;
pre=pre->next;
m--;
}
while(cur->next&&flag!=0)
{
ListNode* last = cur->next;
cur->next=last->next;
last->next=pre->next;
pre->next=last;
flag--;
}
return dummy->next;
}
143 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
解答：
将原来的链表全部塞入双端队列，然后从前后分别放出。
注意：
- while里面要双重判断
- 最后要处理一下屁股
void reorderList(ListNode* head) {
//双端队列
if (head == NULL) return;
deque<ListNode*> de;
ListNode* pre = new ListNode(0);
pre->next = head;
ListNode* dummy = pre;
while (dummy->next != NULL)
{
de.push_back(dummy->next);
dummy = dummy->next;
}
while (1)
{
if (de.empty()) break;
pre->next = de.front();
de.pop_front();
pre = pre->next;
//再后，这里判断一下是不是空了
if (de.empty()) break;
pre->next = de.back();
de.pop_back();
pre = pre->next;
}
//把屁股处理一下
pre->next = NULL;
}
203 移除链表元素
除链表中等于给定值 val 的所有节点。
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解答：
ListNode* removeElements(ListNode* head, int val) {
ListNode* pre = new ListNode(0);
pre->next = head;
ListNode* dummy = pre;
while (pre->next != NULL)
{
if (pre->next->val == val)
pre->next = pre->next->next;
else
pre = pre->next;
}
return dummy->next;
}
2. 快慢指针
019 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
解答：
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head) return NULL;
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* fast=pre;
ListNode* slow=pre;
for(int i=0;i<n;i++)
fast=fast->next;
while(fast->next)
{
slow=slow->next;
fast=fast->next;
}
//注意！！！
slow->next=slow->next->next;
return pre->next;
}
061 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
解答：
ListNode* rotateRight(ListNode* head, int k) {
ListNode* pre = new ListNode(0);
if (!head) return NULL;
pre->next = head;
ListNode* fast = pre;
ListNode* slow = pre;
int len = 0;
while (fast->next != NULL)
{
fast = fast->next;
len++;
}
int jump = len - (k % len);
while (jump > 0)
{
jump--;
slow = slow->next;
}
// 输入: pre->1->2->3->4->5->NULL, k = 2
// slow fast
// 输出: pre->4->5->1->2->3->NULL*/
fast->next = pre->next;
pre->next = slow->next;
slow->next = NULL;
return pre->next;
}
109 有序链表转化为二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解答：
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
else if(head.next == null) return new TreeNode(head.val);
ListNode pre = head;
ListNode p = pre.next;
ListNode q = p.next;
//找到链表的中点p
while(q!=null && q.next!=null){
pre = pre.next;
p = pre.next;
q = q.next.next;
}
//将中点左边的链表分开
pre.next = null;
TreeNode root = new TreeNode(p.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(p.next);
return root;
}
141 环形链表
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
输入：head = [3,2,0,-4], pos = 1
输出：true
解答：
bool hasCycle(ListNode* head)
{
ListNode* fast=head;
ListNode* slow=head;
while (fast != NULL && fast->next != NULL)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
142 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
解答：
ListNode *detectCycle(ListNode *head) {
set<ListNode*> s;
ListNode* index=head;
while(index)
{
if(!s.count(index))
{
s.insert(index);
index=index->next;
}
else
return index;
}
return nullptr;
}
148 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
输入: -1->5->3->4->0
输出: -1->0->3->4->5
解答：
归并排序
//[ivan_allen]https://leetcode-cn.com/problems/sort-list/comments/
ListNode* sortList(ListNode* head) {
ListNode* p = head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
int len = 0;
while (p)
{
len++;
p = p->next;
}
for (int size = 1; size < len; size = size << 1)
{
ListNode* cur = dummy->next;
ListNode* tail = dummy;
while (cur)
{
auto left = cur;
auto right = cut(left, size);
cur = cut(right, size);//移动到下一个地方
tail->next = merge(left, right);
while (tail->next)
tail = tail->next;
}
}
return dummy->next;
}
ListNode* cut(ListNode* head, int n)
{
ListNode* first = head;
//--n！！！
while (--n && first)
{
first = first->next;
}
if (!first)
return nullptr;
//second为第二链表开头，first为第一
ListNode* second = first->next;
first->next = nullptr;
return second;
}
ListNode* merge(ListNode* l1, ListNode* l2)
{
ListNode* pre = new ListNode(0);
ListNode* dummy = pre;
while (l1 && l2)
{
int val1 = l1->val;
int val2 = l2->val;
if (val1 > val2)
{
pre->next = l2;
pre = l2;
l2 = l2->next;
}
else
{
pre->next = l1;
pre = l1;
l1 = l1->next;
}
}
if (l1)
pre->next = l1;
else
pre->next = l2;
return dummy->next;
}
234 回文链表
请判断一个链表是否为回文链表。
输入: 1->2->2->1
输出: true
解答：
bool isPalindrome(ListNode* head) {
ListNode* pre=new ListNode(0);
pre->next=head;
ListNode* fast=pre;
ListNode* slow=pre;
stack<ListNode*> stk;
while(fast!=NULL&&fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
stk.push(slow);
}
//bool isEven=false;
if(fast==NULL)
stk.pop();
while(slow->next)
{
ListNode* cur=stk.top();
stk.pop();
if(cur->val!=slow->next->val)
return false;
slow=slow->next;
}
return true;
}
3. 其他类型
160 相交链表
编写一个程序，找到两个单链表相交的起始节点。
题解：
一定要保证每个引导指针都能跑到NULL节点，即使两个不相干的链表也能将NULL视为相交节点！
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* index1 = headA;
ListNode* index2 = headB;
if (index1 == NULL || index2 == NULL)
return NULL;
//如果长度相同没有交点，第一轮后同时为NULL，退出
//如果长度不同没有交点，第二轮后两者移动相同距离
//同时为NULL，退出
while (index1 != index2)
{
//必须写index1而不是index1->next，不然没法出NULL
index1 = (index1 == NULL) ? headB : index1->next;
index2 = (index2 == NULL) ? headA : index2->next;
}
return index1;
}
237 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
解答：
node=node->next不行，要改为指针传递或引用传递。
void deleteNode(ListNode* node) {
*node=*node->next;
}