（一）LeetCode206.反转链表
题目描述：
反转一个单链表。
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode* reverseList(ListNode* head)//非递归版本
{
if (head == NULL)
return head;
ListNode * pre = NULL;
ListNode * p = head;
while (p)
{
ListNode *tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
return pre;
}
ListNode* reverseList1(ListNode* head)//递归版本
{
if (head == NULL || head->next == NULL)
return head;
ListNode *newHead = reverseList(head->next);
//反转指针
ListNode * tmp = head->next;
tmp->next = head;
head->next = NULL;
return newHead;
}
（二）LeetCode160. 相交链表
题目描述
编写一个程序，找到两个单链表相交的起始节点。
思路
假设链表A与B一共有三部分构成，A独有的结点个数为a，B独有的结点个数为b，A,B公有的结点个数为c.
则有 a+c+b=b+c+a
那么可以用两个指针p,q，分别从A,B的头结点开始，当p指向空的时候，将p指向B的头结点，同理当q指向空的时候，将q指向A的头结点。
如果两个链表有相交部分，他们一定会相遇，如果没有，最后都同时为空。
代码
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode * p = headA;
ListNode * q = headB;
if (!p || !q)
return NULL;
while (p != q)
{
if (!p)
p = headB;
else
p = p->next;
if (!q)
q = headA;
else
q = q->next;
}
return p;
}
（三）LeetCode142. 环形链表 II
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
思路
快慢指针即可解决，快指针走两步，慢指针走一步。假如有环，那么两个指针一定会相遇
证明
假如存在环，可以将问题看出快指针在追赶慢指针。
- 快指针与慢指针之间差1步。此时继续往后走，慢指针前进1步，快指针前进2步，两者相遇。
- 快指针与慢指针之间差2步。此时继续往后走，慢指针前进1步，快指针前进2步，两者之间相差1步，转化为第1种情况。
- 快指针与慢指针之间差n步。此时继续往后走，慢指针前进1步，快指针前进2步，两者之间相差
(n+1-2)步。
寻找环入口
假如快慢指针在环的i个结点相遇，假设慢指针一共走了n步，那么快指针走了2n步，因为快指针的速度是其两倍，那么慢指针再走n步(刚好是2n步），肯定还是在i点，所以可以得到环的大小为n。
我们假设环入口与结点i的距离为k，起点距离环入口距离为l,
那么根据上述有n=l+k（慢指针第一次走n步），则l=n-k
所以，我们用两个指针，分别从起点和相遇点同时走，则一定在环入口相遇
因为相遇点距离环入口：n-k
起点距离环入口：l
代码
ListNode *detectCycle (ListNode *head)
{
if (head == NULL || head->next == NULL)
return NULL;
ListNode * fast = head->next->next;
ListNode * slow = head->next;
while (fast != slow)
{
if (fast == NULL || slow == NULL || fast->next == NULL)
return NULL;
fast = fast->next->next;
slow = slow->next;
}
fast = head;
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
（四）LeetCode234. 回文链表
题目描述
判断一个链表是否为回文链表。
思路
将链表后半段原地翻转，再将前半段、后半段依次比较，判断是否相等
代码
//链表后半段原地翻转，再将前半段、后半段依次比较，判断是否相等
bool isPalindrome(ListNode* head)
{
//如果链表为空或者仅有一个元素那么肯定是回文链表
if (!head || !head->next)
return true;
//快慢指针法，寻找链表中心
ListNode * slow, *fast;
slow = fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
if (fast) //链表元素奇数个
{
slow->next = reverseList(slow->next);
slow = slow->next;
}
else//链表元素偶数个
slow = reverseList(slow);
//slow此时为链表后半段第一个元素
while (slow)
{
if (head->val != slow->val)
{
return false;
}
slow = slow->next;
head = head->next;
}
return true;
}
//非递归版本的反转链表
ListNode* reverseList(ListNode* head)
{
if (head == NULL)
return head;
ListNode * pre = NULL;
ListNode * p = head;
while (p)
{
ListNode *tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
return pre;
}
（五）LeetCode109. 有序链表转换二叉搜索树
题目描述
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
思路
链表有序，二叉搜索树的左子树小于根结点，右子树大于根结点，又需要满足AVL的性质。
则找到链表中间元素，设为根结点，前半段为左子树，后半段为右子树，递归即可。
代码
TreeNode* sortedListToBST(ListNode* head)
{
if (!head)
return NULL;
if (!head->next)
{
TreeNode * root = new TreeNode(head->val);
return root;
}
//快慢指针法，寻找链表中心
ListNode * slow, *fast;
slow = fast = head;
ListNode * tail = head;//保存前半段的尾巴
while (fast && fast->next)
{
tail = slow;
slow = slow->next;
fast = fast->next->next;
}
tail->next = NULL;//前半段
TreeNode * root = new TreeNode(slow->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(slow->next);
return root;
}
（六）LeetCode24. 两两交换链表中的节点
题目描述
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
思路
三个指针，p表示上一组交换完成后的后面结点，l，r表示当前交换的左右结点
交换过程可以简化为：p指向r，r指向l即可，最后将p指向NULL
注意处理奇数长度的情况
代码
ListNode* swapPairs(ListNode* head)
{
if (!head || !head->next)
return head;
ListNode *p, *l, *r; //p表示上一组交换完成后的后面结点，l，r表示当前交换的左右结点
p = NULL, l = head, r = head->next;
head = head->next; //头结点更换位置
ListNode *l1, *r1; //记录下两组需要交换的结点
while (l && r)
{
l1 = r->next;
r1 = l1 ? l1->next : NULL;
if (p)//上一组交换完成后的后结点的 next指向当前交换后的前结点
p->next = r;
r->next = l;//r指向l
p = l;//保存当前交换后的后结点
l = l1;
r = r1;
}
if (l)//奇数长度情况
{
p->next = l;
p = l;
}
p->next = NULL;//链表尾端
return head;
}
（七）LeetCode328. 奇偶链表
题目描述
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
思路
用两个指针odd,even分别表示奇数指针和偶数指针
先更新odd的next,然后更新odd
再更新even的next,然后更新even
代码
ListNode* oddEvenList(ListNode* head)
{
if (!head || !head->next)
return head;
ListNode *odd = head;//奇数结点
ListNode * even = head->next;//偶数结点
ListNode * evenHead = head->next;//偶数头结点
while (odd->next && even->next)
{
//奇数结点下一个指向偶数结点的下一个元素
odd->next = even->next;//更新奇数结点的next
odd = odd->next;//更新奇数结点
//偶数结点下一个指向新的奇数结点的下一个元素
even->next = odd->next;//更新偶数结点的next
even = even->next;//更新偶数结点
}
odd->next = evenHead;//连接奇数和偶数两个链表
return head;
}
（八）LeetCode143. 重排链表
题目描述
给定一个单链表 L：L0→L1→…→Ln-1→Ln，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
思路
- 把整个链表划分成2个等长的子链表，如果原链表长度为奇数，那么第一个子链表的长度多1。
- 翻转第二个子链表。
- 将两个子链表合并。
代码
ListNode * reorderList (ListNode* head)
{
if (!head || !head->next)
return head;
ListNode * fast = head;
ListNode * slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
//利用快慢指针找到中心位置，翻转后面链表
ListNode * mid = reverseList (slow->next);
slow->next = NULL;
//合并p和q，p的长度 = q的长度 | q的长度 +1
ListNode * p, *q;
p = head->next;
q = mid;
ListNode *t = head;
while (p && q)
{
t->next = q;
t = t->next;
q = q->next;
t->next = p;
t = t->next;
p = p->next;
}
return head;
}
ListNode * reverseList (ListNode * head)
{
if (!head || !head->next)
return head;
ListNode * pre = NULL;
ListNode * p = head;
while (p)
{
ListNode * tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
return pre;
}
（九）LeetCode445. 两数相加 II
题目描述
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
思路
简单的大数相加，首先各自翻转，然后逐位想加，最后处理进位，需要注意最高位进位时需要new一个新的结点，再翻转回去即可。
代码
ListNode* addTwoNumbers (ListNode* l1, ListNode* l2)
{
if (!l1 || !l2)
return !l1 ? l2 : l1;
//首先各自翻转
l1 = reverseList (l1);
l2 = reverseList (l2);
ListNode * head = new ListNode (l1->val + l2->val);
ListNode * sum = head;
ListNode * p = l1->next;
ListNode * q = l2->next;
//然后逐位相加
while (p || q)//
{
ListNode * tmp = new ListNode (0);
tmp->val = (p ? p->val : 0) + (q ? q->val : 0);
sum->next = tmp;
sum = sum->next;
p = p ? p->next : NULL;
q = q ? q->next : NULL;
}
sum->next = NULL;
//最后处理进位
p = head;
while (p->next)
{
if (p->val >= 10)
{
p->val -= 10;
p->next->val += 1;
}
p = p->next;
}
if (p->val >= 10) //最后一位数需要进位
{
p->val -= 10;
ListNode * tmp = new ListNode (1);
p->next = tmp;
p = p->next;
p->next = NULL;
}
//翻转回去
head = reverseList (head);
return head;
}
ListNode * reverseList (ListNode * head)
{
if (!head || !head->next)
return head;
ListNode * pre = NULL;
ListNode * p = head;
while (p)
{
ListNode * tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
return pre;
}
（十）LeetCode725. Split Linked List in Parts
题目描述
要求将链表进行分割，使分割的部分尽可能一样，如果不是平均分，应使任意部分大小不相差1，如果要求的分割段数小于链表的元素数，则末尾用nullptr填充。
思路
求出链表的长度，对k求除数和余数，商res代表分割的长度，余数mod表示前mod分割块的长度要+1。
代码
vector<ListNode*> splitListToParts (ListNode* root, int k)
{
vector<ListNode*> vec (k, nullptr);
if (!root)
return vec;
ListNode * p = root;
int len = 0;
while (p)
{
len++;
p = p->next;
}
int res = len / k;
int mod = len % k;
p = root;
if (res == 0)//链表长度小于k
{
ListNode * nxt = p->next;
for (int i = 0; i < len; i++)
{
vec[i] = p;
nxt = p->next;
p->next = NULL;
p = nxt;
}
return vec;
}
for (int i = 0; i < k; i++)
{
int tmp = res + (i < mod ? 1 : 0);
vec[i] = p;
tmp--; //少走一步，方便保存下一个结点和将当前部分的末尾置为空
while (tmp--)
{
p = p->next;
}
ListNode * nxt = p->next;
p->next = NULL;
p = nxt;
}
return vec;
}
（十一）LeetCode148. 排序链表
题目描述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
思路
链表归并排序模板题。
代码
ListNode* sortList (ListNode* head)
{
if (!head || !head->next)
return head;
ListNode * fast = head;
ListNode * slow = head;
ListNode * pre = NULL;
while (fast && fast->next)
{
pre = slow;
fast = fast->next->next;
slow = slow->next;
}
pre->next = NULL;
return mergeTwoLists (sortList (head), sortList (slow));
}
ListNode* mergeTwoLists (ListNode* l1, ListNode* l2)
{
if (l1 == NULL || l2 == NULL)
{
return l1 == NULL ? l2 : l1;
}
ListNode * head = new ListNode (0);
ListNode * p = head;
while (l1 && l2)
{
if (l1->val <= l2->val)
{
p->next = l1;
l1 = l1->next;
}
else
{
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 == NULL ? l2 : l1;
return head->next;
}
（十二）LeetCode817. Linked List Components
题目描述
给出一个链表和一个数组,寻找有几个component, 每一个component的val必须在数组G中而且在链表中是连接的。
思路
遍历链表，使用tar变量来标记，初始化为0，查看链表中当前元素在是否在集合中
- 假如不在集合中，如果tar为0，表示前面没有找到或者已经处理了；tar为1则表示前面的component结束了，则res++,并将tar置为0；
- 假如在集合中，将tar置为1即可。
代码
int numComponents (ListNode* head, vector<int>& G)
{
if (!head || !G.size())
return 0;
set<int > S;
for (int i = 0; i < G.size(); i++)
S.insert (G[i]);
ListNode * p = head;
int tar = 0;
int res = 0;
while (p)
{
if (S.find (p->val) != S.end()) //查找成功
tar = 1;
else
{
if (tar)
{
tar = 0;
res++;
}
}
p = p->next;
}
if (tar == 1)
res++;
return res;
}
（十三）LeetCode147. 对链表进行插入排序
题目描述
对链表进行插入排序。
思路
直接模拟插入排序过程即可
代码
ListNode* insertionSortList (ListNode* head)
{
if (!head || !head->next)
return head;
ListNode * q = head->next;//q表示当前需要排序的元素
ListNode * qPre = head;//表示已经排好序的最后一个元素，也就是q的前一个元素
while (q)
{
ListNode * p = head, *pPre = NULL;//pPre表示p的前一个元素
while (p != q)
{
if (p->val > q->val)//需要将q插入到p前面
{
ListNode * tmp = q->next;//保存q的next信息
if (!pPre)//q作为头结点
head = q;
else//p的前一个元素指向q
pPre->next = q;
q->next = p;//q指向p
qPre->next = tmp;//已经排好序的最后一个元素指向tmp（原来q的next）
q = qPre;//恢复位置，继续循环
break;
}
pPre = p;
p = p->next;
}
qPre = q;
q = q->next;
}
return head;
}
（十四）LeetCode86. 分隔链表
题目描述
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
应当保留两个分区中每个节点的初始相对位置。
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
思路
分别用两个链表记录在左边还是右边，最后将左右两个链表合并即可。
代码
ListNode* partition (ListNode* head, int x)
{
if (!head || !head->next)
return head;
ListNode * leftHead = NULL, * rightHead = NULL;
ListNode * left = NULL, * right = NULL;
ListNode * p = head;
while (p)
{
if (p->val < x)
{
if (!left)
{
left = p;
leftHead = p;
}
else
{
left->next = p;
left = left->next;
}
}
else
{
if (!right)
{
right = p;
rightHead = p;
}
else
{
right->next = p;
right = right->next;
}
}
p = p->next;
}
if (!right)
{
left->next = NULL;
return leftHead;
}
right->next = NULL;
if (!left)
return rightHead;
left->next = rightHead;
return leftHead;
}
（十五）LeetCode92. 反转链表 II&LeetCode25. k个一组翻转链表
题目描述
- 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
- 给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。
思路
- 处理好细节即可，将需要反转的区间断开，将断开出的结点信息保存下来,然后反转对应的区间，最后在将该区间插入到原来的位置
- 第二题需要用到第一题的解法，即每k个反转一次，转化成对应区间的反转，调用第一题的代码即可
代码
ListNode* reverseKGroup (ListNode* head, int k)//K个一组反转链表
{
if (!head || !head->next)
return head;
ListNode * p = head;
int len = 0;
while (p)
{
len++;
p = p->next;
}
if (k > len)
return head;
for (int i = 1; i + k - 1 <= len; i += k)
{
//反转从位置 i 到 i+k-1 的链表
head = reverseBetween (head, i, i + k - 1);
}
return head;
}
ListNode* reverseBetween (ListNode* head, int m, int n)//反转从位置 m 到 n 的链表
{
if (!head || !head->next)
return head;
int cnt = 1;
ListNode * p = head, * pre = NULL;
//分别表示翻转前面的最后一个结点，翻转后面的第一个结点，和需要翻转的第一个结点
ListNode * preTail = NULL, * nextHead = NULL, * revHead = NULL;
while (p)
{
if (cnt == m)
{
preTail = pre;//保存翻转前的最后一个结点
revHead = p;//从该结点开始翻转
}
if (cnt == n)
{
nextHead = p->next;//保存翻转后面的第一个结点
p->next = NULL;//使得翻转的部分隔开
break;
}
pre = p;
p = p->next;
cnt++;
}
revHead = reverseList (revHead);
p = revHead;
while (p->next)//找到翻转部分最后一个元素
p = p->next;
if (!preTail)//从第一个元素翻转则需更新头结点
head = revHead;
else
preTail->next = revHead;
p->next = nextHead;
return head;
}
ListNode * reverseList (ListNode * head)//反转链表
{
if (!head || !head->next)
return head;
ListNode * pre = NULL;
ListNode * p = head;
while (p)
{
ListNode * tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
return pre;
}
（十六）LeetCode61. 旋转链表
题目描述
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
思路
链表每个节点向右移动 k 个位置,可以理解为将链表前len-k个元素放在了链表的末尾。
因为这样对第一个结点来说，他现在的位置正好处于没有移动的k个元素后面。
代码
ListNode* rotateRight (ListNode* head, int k)
{
if (!head || !head->next || !k)
return head;
int len = 0;
ListNode * p = head;
ListNode * tail = head;
while (tail->next)//找到末尾结点
{
len++;
tail = tail->next;
}
len++;
k = k % len;
if (!k)
return head;
k = len - k;//向右旋转k步可以理解成将前len-k个元素放到链表尾部
p = head;
int cnt = 1;
ListNode * newHead = NULL;
while (p)
{
if (cnt == k)
{
newHead = p->next;
p->next = NULL;
break;
}
cnt++;
p = p->next;
}
tail->next = head;
return newHead;
}
（十七）LeetCode82. 删除排序链表中的重复元素 II&LeetCode19. 删除链表的倒数第N个节点
题目描述
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
思路
注意细节，小心头结点
删除链表的倒数第N个节点时，用两个指针，第一个先走N步，然后一起走，第一个指针为空时，第二个指针则为倒数第N个结点。
代码
ListNode* deleteDuplicates (ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode * pre = NULL;
ListNode * p = head;
ListNode * next = NULL;
while (p)
{
bool flag = false;
next = p->next;
while (next && next->val == p->val)
{
flag = true;
next = next->next;
}
if (flag) //需要删除
{
if (pre == NULL) //头结点也需要删除
head = next;
else
pre->next = next;
}
else//不需要删除，更新pre
pre = p;
p = next;
}
return head;
}
ListNode* removeNthFromEnd (ListNode* head, int n)
{
if (!head)
return NULL;
ListNode * p1 = head;
while (n--)
p1 = p1->next;
if (!p1)
return head->next;
ListNode * p2 = head;
ListNode * pre = NULL;
while (p1 && p2)
{
p1 = p1->next;
pre = p2;
p2 = p2->next;
}
//删除p2
pre->next = p2->next;
return head;
}
（十八）LeetCode138. 复制带随机指针的链表
题目描述
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。
思路
可以用哈希表保存随机指针，更简单的解法是：
- 首先在每个结点后面复制一个当前结点，并将其插入到该结点后面。
- 更新复制结点的random信息，注意细节
- 将链表一分为二，即将原链表中的奇数结点和偶数结点构成两个链表，返回偶数结点构成的链表即可。
代码
RandomListNode *copyRandomList (RandomListNode *head)
{
if (!head)
return NULL;
RandomListNode * p = head;
while (p)//在每个结点后面复制一个当前结点
{
RandomListNode * node = new RandomListNode (p->label);
node->next = p->next;
p->next = node;
p = node->next;
}
p = head;
while (p)//更新复制后的结点的random指针
{
if (p->random)
p->next->random = p->random->next;
p = p->next->next;
}
RandomListNode * newHead = head->next;
p = head;
while (p)//将链表一分为二
{
RandomListNode * tmp = p->next;
p->next = p->next ? p->next->next : NULL;
p = tmp;
}
return newHead;
}
（十九）LeetCode23. 合并K个排序链表
题目描述
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
思路
常规解法
可以用归并排序的思想。
首先将k个链表两两合并成k/2个新链表，然后将k/2个链表两两合并成k/4个新链表
如此继续直到最终只有一个链表即为结果。
高效解法---优先级队列实现
优先级队列的优先级情况：堆顶始终为最小的结点，空结点在堆底
首先将所有头结点压入优先级队列，然后逐个弹出，插入新的链表，同时将弹出的结点的next压入优先级队列
直到优先级队列为空集或者队首元素为空则结束
代码
//法一 常规解法
ListNode* mergeKLists (vector<ListNode*>& lists)
{
if (!lists.size())
return NULL;
int low=0,high=lists.size()-1;
while(high)
{
low=0;//low重置为0，继续合并
while(low<high)
{
//合并后保存在low中
lists[low]=mergeTwoLists(lists[low],lists[high]);
low++;
high--;
}
}
return lists[0];
}
ListNode* mergeTwoLists (ListNode* l1, ListNode* l2)//合并两个排序链表
{
if (l1 == NULL || l2 == NULL)
{
return l1 == NULL ? l2 : l1;
}
ListNode * head = new ListNode (0);
ListNode * p = head;
while (l1 && l2)
{
if (l1->val <= l2->val)
{
p->next = l1;
l1 = l1->next;
}
else
{
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 == NULL ? l2 : l1;
return head->next;
}
//法二 优先级队列实现
struct cmp //自定义优先级
{
bool operator () (ListNode * l1, ListNode * l2) // 重载括号
{
if (!l1 || !l2)
return !l1;//NULL置于堆底
return l1->val > l2->val; // 等同于greater, 堆顶元素是最小值
}
};
ListNode* mergeKLists (vector<ListNode*>& lists)
{
if (!lists.size())
return NULL;
priority_queue<ListNode *, vector<ListNode * >, cmp > Q; //优先级队列
for (int i = 0; i < lists.size(); i++) //将每个序列的头结点插入优先级队列
Q.push (lists[i]);
ListNode * head = new ListNode (-1); //伪头结点
ListNode * p = head;
while (!Q.empty() && Q.top())
{
ListNode * tmp = Q.top();
Q.pop();
p->next = tmp;
p = p->next;
Q.push (tmp->next);
}
return head->next;
}
