链表问题是c/c++技术岗面试过程中的重点问题，通过对各种链表操作的考察，能够反映出面试者对编程语言掌握的熟练程度，对链表数据结构和指针、地址等概念的理解。
===
Index
链表定义
采用leetcode中的链表通用定义。
struct ListNode{
int val;
ListNode * next;
ListNode(int v):val(v),next(nullptr){}
};
反转
单链表反转
题目描述： 给定一个单向链表的头节点，将链表反转，并返回头节点。
分析： 链表反转类问题一般需要用到三个临时指针，pre，cur,next，使用三个指针对链表进行一次循环即可反转，同时为了便于操作，一般会设一个dummyHead节点，其next指针指向head节点。
实现代码:
ListNode* reverseList(ListNode* head){
if(head == nullptr || head->next == nullptr) return head;
ListNode* pre = nullptr, *p = head, *next = p->next;
while(p){
next = p->next;
p->next = pre;
pre = p;
p = next;
}
return pre;
}
递归写法：
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* res = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return res;
}
反转从位置m到n的链表
题目描述： 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。1 ≤ m ≤ n ≤ 链表长度。
示例：输入：1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
ListNode* reverseBetween(ListNode* head, int m, int n) {
auto dummy = ListNode(-1);
dummy.next = head;
auto p = &dummy;
for (int i = 0; i < m - 1; ++i) p = p->next;
auto cur = p->next, next = cur->next;
for (int i = 0; i < n - m; ++i) {
auto d = next->next;
next->next = cur;
cur = next, next = d;
}
p->next->next = next;
p->next = cur;
return dummy.next;
}
k个一组翻转链表
题目描述： 给你一个链表，每k个节点一组进行翻转，k是不大于链表长度的正整数，如果节点总数不是k的整数倍，那么请将剩余的节点保持原有顺序。
1. 递归法
ListNode* reverseKGroup(ListNode* head, int k) {
auto p = head;
for (int i = 0; i < k; ++i) {
if (!p) return head; //不够k个，不反转
p = p->next;
}
ListNode *cur = head, *pre = nullptr, *nxt;
for (int i = 0; i < k; ++i) { // 反转k个
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
head->next = reverseKGroup(cur, k); //递归处理后面部分
return pre;
}
2. 迭代方法
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || !head->next || k < 2) return head;
ListNode preHead(-1);
preHead.next = head;
ListNode *cur = &preHead, *pre = &preHead, *next;
int cnt = 0;
while ((cur = cur->next)) cnt++; //链表中节点个数
while (cnt >= k) {
cur = pre->next;
next = cur->next;
for (int i = 0; i < k - 1; ++i) {
cur->next = next->next;
next->next = pre->next;
pre->next = next;
next = cur->next;
}
pre = cur; cnt -= k;
}
return preHead.next;
}
两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例
- 输入 ： 1 2 3 4
- 输出 ： 2 1 4 3
1.递归法
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
ListNode *pre = head, *cur = head->next, *next = cur->next;
pre->next = swapPairs(next);
cur->next = pre;
return cur;
}
2.迭代法
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode * dummyhead = new ListNode(-1);
dummyhead->next = head;
ListNode * prev = dummyhead, *p = head, * next_p = head->next;
while(next_p){
prev->next = next_p;
p->next = next_p->next;
next_p->next = p;
prev = p;
p = p->next;
if(p)
next_p = p->next;
else
next_p = nullptr;
}
return dummyhead->next;
}
旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
ListNode* rotateRight(ListNode* head, int k) {
if (!head || !head->next || k == 0) return head;
ListNode *cur = head;
int len = 1;
while (cur->next && ++len) cur = cur->next;
cur->next = head;
k = len - k % len;
while (k--) cur = cur->next;
head = cur->next;
cur->next = nullptr;
return head;
}
删除节点
o1时间内删除链表节点
题目描述： 给定链表中间的某个节点指针，在O(1)时间内删除该节点。假定你只能访问该节点。
分析： 在这个问题里，由于访问不到该节点的前一个节点，所以 这题对尾节点是无解的 。要删除当前节点，直接将其next节点的值复制到当前节点，然后删除后继节点。
实现代码：
bool deleteListNode(ListNode * cur){
if(cur == nullptr || cur->next == nullptr)
return false;
ListNode * pNext = cur->next;
cur->val = pNext->val;
cur->next = pNext->next;
delete pNext;
return true;
}
删除排序链表中重复元素
题目描述： 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
分析： 双指针法，将相同的第一个节点的next指针指向下一个不同的节点或者NULL
ListNode* deleteDuplicates(ListNode* head) {
ListNode *cur = head;
while (cur && cur->next) {
if (cur->val == cur->next->val)
cur->next = cur->next->next;
else
cur = cur->next;
}
return head;
}
删除排序链表中的重复元素2
题目描述： 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
ListNode* deleteDuplicates(ListNode* head) {
if (!head|| !head->next) return head;
ListNode dummy(0); dummy.next = head;
ListNode* cur = head; ListNode* prev = &dummy;
while (cur && cur->next){
if (cur->next->val == cur->val) {
int val = cur->val;
while (cur && cur->val == val) {
prev->next = cur->next;
delete cur;
cur = prev->next;
}
} else {
prev = cur;
cur = cur->next;
}
}
return dummy.next;
}
链表查找
求链表的倒数第k个节点
题目描述： 输入一个单向链表，输出该链表中倒数第k个节点。
分析： 快慢指针法，设置两个指针slow,fast，初始时都指向head，先让fast走k步，然后slow,fast同时走，当fast走到链表末尾时，slow就是倒数第k个节点。
ListNode* findkthNode(ListNode *head, int k){
if(k < 0 || head == nullptr) return nullptr;
ListNode* slow, *fast;
slow = fast = head;
int i = k;
while(i > 0 && fast){
fast = fast->next;
i--;
}
if(i > 0) return nullptr;
while(fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
求链表的中间节点
题目描述： 求链表的中间节点，，如果链表长度为偶数，返回中间两个节点的任意一个，若为奇数，返回中间节点。
分析： 快慢指针法，fast每次移动两部，slow每次移动一步。
ListNode* findMiddleNode(Node* head){
if(head == nullptr) return nullptr;
ListNode* slow, *fast;
slow = fast = head;
while(fast != nullptr && fast->next != nullptr){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
交换链表中的节点
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例
- 输入：1 2 3 4 2 k = 2
- 输入：1 4 3 2 5
ListNode* swapNodes(ListNode* head, int k) {
auto fast = head;
for(int i = 1 ; i < k ; i ++){
fast = fast->next;
}
auto temp = fast, slow = head;
while(fast->next){
fast = fast->next;
slow = slow->next;
}
swap(slow->val, temp->val);
return head;
}
环形/相交链表
判断单链表是否有环
题目描述： 输入一个单向链表，判断链表是否有环。 分析： 快慢指针，如果存在环，那么两个指针必会在环中相遇。
bool hasCircle(ListNode *head){
Node *slow = head, *fast = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
return true;
}
}
return false;
}
找到环的入口
题目描述： 输入一个单向链表，判断链表是否有环，如果存在环，找到环的入口。
分析: 快慢指针,如果快慢指针相遇，则有环，这是将其任意一个设为head，按相同速度走，则其再次相遇时，即为环的入口。
ListNode *detectCycle(ListNode *head) {
ListNode * fast = head, *slow = head;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
fast = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return fast;
}
}
return nullptr;
}
判断两个链表是否相交
题目描述： 给出两个单链表的头指针，判断两个链表是否相交，假设两个链表均不带环。 分析: 如过两个链表相交，则从交点到链表末尾都是公共的，所以只需要判断两个链表的末尾节点是否相同。 时间复杂度O(len1+len2)，空间复杂度O(1)。
bool isIntersect(ListNode* h1, ListNode* h2){
if(h1 == nullptr || h2 == nullptr) return false;
while(h1->next) h1 = h1->next;
while(h2->next) h2 = h2->next;
return h1 == h2;
}
有环链表判断相交
题目描述: 对第7题，如果链表是有环的，该怎么做？
分析： 如果两个链表有环且相交，则两个链表有共同一个环，因此可以一个链表上两个指针相遇的节点，在不在另一个链表上。
bool isIntersectWithCircle(ListNode* h1, ListNode* h2){
ListNode * p1 = detectCycle(h1); *p2 = detectCycle(h2);
if(!p1 || !p2) return false;
ListNode * tmp = p2->next;
while(tmp != p2){
if(tmp == p1)
return true;
tmp = tmp->next;
}
return false;
}
两个链表相交的第一个公共节点
题目描述: 如果两个无环单链表相交，求出它们第一个公共节点。
分析： 计算两个链表长度l1和l2，将较长链表像后移动l2-l1个节点，然后同时移动两个指针，直到相等。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *h1 = headA, *h2 = headB;
while(h1 != h2){
h1 = h1 ? h1->next : headB;
h2 = h2 ? h2->next : headA;
}
return h1;
}
链表合并
合并2个有序链表
题目描述： 将两个升序链表合并为一个新的 升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* p = dummy, *cur;
while (l1 && l2) {
cur = (l1->val < l2->val) ? l1 : l2;
p->next = cur;
p = p->next;
cur == l1 ? l1 = l1->next : l2 = l2->next;
}
p->next = l1 ? l1 : l2;
return dummy->next;
}
合并k个有序链表
题目描述： 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
分析： 维护当前每个链表没有被合并的元素的最前面一个，k个链表就最多有 k个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
复杂度：
- 时间复杂度：考虑优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(log k)，这里最多有 kn 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为O(kn×logk)
- 空间复杂度：这里用了优先队列，优先队列中的元素不超过 k个，故渐进空间复杂度为 O(k)。
struct Status {
int val;
ListNode *ptr;
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
};
priority_queue <Status> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (auto node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
auto f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
合并奇偶排序链表
链表奇数位升序，偶数位降序，合并为排序链表
如： 1 8 3 6 5 4 7 2 9
排序后：1 2 3 4 5 6 7 8 9
方法：
- 对链表进行奇偶切分；
- 反转降序链表
- 合并两个升序链表
ListNode* mergeList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *p1 = head, *p = head->next, *p2 = p;
while (p2 && p2->next) { //切分
p1->next = p1->next->next;
p2->next = p2->next->next;
p1 = p1->next; p2 = p2->next;
}
p1->next = nullptr;
if (p && p->next) { //反转
ListNode *pre = nullptr, *cur = p, *next;
while (cur) {
next = cur->next; cur->next = pre;
pre = cur; cur = next;
} p = pre;
}
//合并
ListNode *dummy = new ListNode(-1), *cur;
p1 = head; p2 = p; p = dummy;
while (p1 && p2) {
cur = (p1->val < p2->val) ? p1 : p2;
p->next = cur; p = p->next;
cur == p1 ? p1 = p1->next : p2 = p2->next;
}
p->next = p1 ? p1 : p2;
return dummy->next;
}
链表排序
重排链表
给定链表 L : L0 -> L1 -> ... -> Ln-1 -> Ln,
重新排列为: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
void reorderList(ListNode *head) {
if (!head || !head->next) return;
// 1. find middle node, split
ListNode *p1 = head, *p2 = head->next;
while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
}
p2 = p1->next; p1->next = nullptr;
//2. reverse p2
ListNode *p = p2, *pre = nullptr, *next;
while (p) {
next = p->next; p->next = pre;
pre = p; p = next;
}
//3. merge
ListNode *dummy = new ListNode(-1); dummy->next = head;
p = dummy; p1 = head; p2 = pre;
while (p1 && p2) {
p->next = p1;
p1 = p1->next;
p->next->next = p2;
p = p2;
p2 = p2->next;
}
if (p1) p->next = p1;
}
链表归并
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *fast = head, *slow = head, *pre = NULL;
while(fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;
return merge(sortList(head), sortList(slow));
}
ListNode* merge(ListNode *l1, ListNode *l2) {
if (!l1 || !l2) return l1 ? l1 : l2;
if (l1->val < l2->val) {
l1->next = merge(l1->next, l2);
return l1;
}else {
l2->next = merge(l1, l2->next);
return l2;
}
return l2;
}
链表快排
// 链表范围为 [lo, hi), pre 为 lo 的前置节点
void qsort(ListNode* pre, ListNode* lo, ListNode* hi) {
if (lo == hi || lo->next == hi) return; // 至少有一个元素
auto mid = partition(pre, lo, hi);
qsort(pre, pre->next, mid); // qsort(pre, lo, mid);
qsort(mid, mid->next, hi);
}
ListNode* partition(ListNode* pre, ListNode* lo, ListNode* hi) {
int key = lo->val;
auto mid = lo; // 不是必须的，直接使用 lo 也可以
ListNode ll(0), rr(0); // 创建两个新链表
auto l = &ll, r = &rr; // ListNode *l = &ll, *r = &rr;
// i 从 lo 的下一个节点开始遍历，因为 lo 是枢纽不参与遍历
for (auto i=lo->next; i != hi; i = i->next) {
if (i->val < key) {
l = l->next = i; // python 中不能这么写
} else {
r = r->next = i; // python 中不能这么写
}
}
// 拼接
r->next = hi;
l->next = mid; // 这里的 mid 实际上就是 lo，即 l->next = lo
mid->next = rr.next;
pre->next = ll.next;
return mid; // 返回中枢
}
ListNode* sortList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode pre(0); // 设置一个新的头结点
pre.next = head;
qsort(&pre, head, nullptr);
return pre.next;
}
其它
回文链表
请判断一个链表是否为回文链表。
bool isPalindrome(ListNode* head) {
ListNode *slow = head, *fast = head, *rev = nullptr;
while (fast && fast->next) { //反转前半部分
fast = fast->next->next;
ListNode *tmp = slow->next;
slow->next = rev;
rev = slow;
slow = tmp;
}
if (fast) slow = slow->next;
while (slow && rev) {
if (slow->val != rev->val) return false;
slow = slow->next;
rev = rev->next;
}
return true;
}
复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
链表节点定义为:
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
Node* copyRandomList(Node* head) {
Node *newHead, *l1, *l2;
if (!head) return head; //将每个节点复制一遍
for (l1 = head; l1; l1 = l1->next->next) {
l2 = new Node(l1->val);
l2->next = l1->next;
l1->next = l2;
}
newHead = head->next; //复制random指针
for (l1 = head; l1; l1 = l1->next->next) {
if (l1->random) l1->next->random = l1->random->next;
}
//分离复制的链表
for (l1 = head; l1; l1 = l1->next) {
l2 = l1->next;
l1->next = l2->next;
if (l2->next) l2->next = l2->next->next;
}
return newHead;
}
二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
Node* treeToDoublyList(Node* root) {
if(!root) return root;
stack<Node*> st;
Node *pre = NULL, *p = root;
while (p || !st.empty()) {
while(p) {
st.push(p); p = p->left;
}
if (!st.empty()) {
p = st.top(); st.pop();
if (!pre) {
pre = p; root = p;
} else {
pre->right = p;
p->left = pre; pre = p;
}
p = p->right;
}
}
pre->right = root;
root->left = pre;
return root;
}
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *p1 = head, *p = head->next, *p2 = p;
while (p2 && p2->next) {
p1->next = p1->next->next;
p2->next = p2->next->next;
p1 = p1->next;
p2 = p2->next;
}
p1->next = p;
return head;
}
分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例
- 输入：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 *p1 = nullptr, *p2 = nullptr, *p = head;
ListNode *l = nullptr, *r = nullptr;
while (p) {
if (p->val < x) {
if (!p1) {
p1 = p; l = p;
} else {
l->next = p; l = p;
}
} else {
if (!p2) {
p2 = p; r = p;
} else {
r->next = p; r = r->next;
}
}
p = p->next;
}
if (p2) r->next = nullptr;
if (p1) l->next = p2;
return p1 ? p1 : p2;
}
链表采样
给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。
进阶: 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？
class Solution {
public:
Solution(ListNode* head) {
list = head;
ListNode* ptr = head;
while (ptr) {
len++;
ptr = ptr->next;
}
}
/** Returns a random node's value. */
int getRandom() {
int rand_index = rand()%len;
ListNode* ptr = list;
for (int i=0; i<rand_index; i++) {
ptr = ptr->next;
}
return ptr->val;
}
private:
int len = 0;
ListNode* list;
};
