本文带来的是以链表为主题的一些经典题目：
链表是一种通过指针串联在一起的线性结构，每一个节点是又两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向NULL（空指针）。链接的入口点称为列表的头结点也就是head。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
链表Python定义方式：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
C++链表定义方式：
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {}; // 节点的构造函数
};
根据列表生成链表，并返回头节点：
def initList(data):
if len(data) == 0:
return
else:
head = ListNode(data[0])
r = head # 头节点
p = head # 指针
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
CPP：根据列表生成链表，这是用来在本地段测试链表有关题目效果的，方便调试。
// 根据列表生成链表，并返回头节点：
ListNode* initList(vector<int>& data) {
if (data.size() == 0) {
return nullptr;
}
ListNode* head = new ListNode(data[0]);
ListNode* cur = head;
for (int i = 1; i < data.size(); i++) {
ListNode* node = new ListNode(data[i]);
cur->next = node;
cur = cur->next;
}
return head;
}
// 根据链表生成数组，并返回数组
vector<int> toVector(ListNode* head) {
ListNode* cur = head;
vector<int> num;
if (head == nullptr) {
return {};
}
while (true) {
num.push_back(cur->val);
if (cur->next == nullptr) break;
cur = cur->next;
}
return num;
}
链表操作中，可以使用原链表来直接进行删除操作，也可以设置一个虚拟头结点在进行删除操作。
在C，C++中，不要忘了还要从内存中删除这两个移除的节点，如果使用java ，python的话就不用手动管理内存了。
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令 dummyHead.next=head.
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy_head = ListNode(next=head)
cur = dummy_head
while cur.next is not None:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_head.next
C++代码如下：
class Solution {
public:
// 设置一个虚拟头结点在进行移除节点操作
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode();
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != nullptr) {
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;
}
// 直接使用原来的链表来进行移除节点操作
ListNode* removeElements2(ListNode* head, int val) {
// 删除头节点
while (head != nullptr && head->val == val) { // 这里不是 if
ListNode* tmp = head;
head = head->next;
delete tmp;
}
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else {
cur = cur->next;
}
}
return head;
}
};
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。单链表：
struct LinkedNode
{
int val;
LinkedNode* next;
LinkedNode() :val(0), next(nullptr) {}
LinkedNode(int x) :val(x), next(nullptr) {}
LinkedNode(int x, LinkedNode* next) :val(x), next(next) {}
};
class MyLinkedList {
public:
MyLinkedList() {
_dummyHead = new LinkedNode();
_size = 0;
}
int get(int index) {
if (index<0 || index >= _size) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while (index--) {
cur = cur->next;
}
return cur->val;
}
void addAtHead(int val) {
LinkedNode* node = new LinkedNode(val);
node->next = _dummyHead->next;
_dummyHead->next = node;
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cur = cur->next;
}
cur->next = newNode;
_size++;
}
void addAtIndex(int index, int val) {
if (index > _size) return;
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* newNode = new LinkedNode(val);
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= _size) {
return;
}
LinkedNode* cur = _dummyHead;
while (index--) {
cur = cur->next;
}
LinkedNode* node = cur->next;
cur->next = cur->next->next;
delete node;
_size--;
}
private:
LinkedNode* _dummyHead;
int _size;
};
双链表比单链表快得多，测试用例花费的时间比单链表快了两倍。但是它更加复杂，它包含了 size，记录链表元素个数，和伪头伪尾。
struct LinkedNode
{
int val;
LinkedNode* next;
LinkedNode* prev;
LinkedNode() :val(0), next(nullptr), prev(nullptr) {}
LinkedNode(int x) :val(x), next(nullptr), prev(nullptr) {}
LinkedNode(int x, LinkedNode* next) :val(x), next(next), prev(nullptr) {}
LinkedNode(int x, LinkedNode* next, LinkedNode* prev) :val(x), next(next), prev(prev) {}
};
class MyLinkedList {
public:
MyLinkedList() {
m_size = 0;
head = new LinkedNode();
tail = new LinkedNode();
head->next = tail;
tail->prev = head;
}
int get(int index) {
if (index < 0 || index >= m_size) {
return -1;
}
LinkedNode* cur = head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
return cur->next->val;
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val, head->next, head);
newNode->next->prev = newNode;
newNode->prev->next = newNode;
m_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val, tail ,tail->prev);
newNode->prev->next = newNode;
newNode->next->prev = newNode;
m_size++;
}
void addAtIndex(int index, int val) {
if (index < 0 || index >m_size) {
return;
}
LinkedNode* cur = head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
LinkedNode* newNode = new LinkedNode(val, cur->next, cur);
newNode->prev->next = newNode;
newNode->next->prev = newNode;
m_size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= m_size) {
return;
}
LinkedNode* cur = head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
LinkedNode* tmp = cur->next;
cur->next = tmp->next;
tmp->next->prev = cur;
delete tmp;
m_size--;
}
private:
int m_size;
LinkedNode* head;
LinkedNode* tail;
};
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
class Solution {
public:
ListNode* reverseList1(ListNode* head) {
ListNode* cur = head;
ListNode* prev = nullptr;
ListNode* tmp = nullptr;
while (cur != nullptr) {
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
// 递归
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
ListNode* reverse(ListNode* pre, ListNode* cur) {
if (cur == nullptr) {
return pre;
}
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
}
};
class Solution {
public:
// 迭代方法：（双指针）
ListNode* reverseList1(ListNode* head) {
ListNode* cur = head;
ListNode* prev = nullptr;
ListNode* tmp = nullptr;
while (cur != nullptr) {
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
}
return prev;
}
// 递归 从后往前翻转指针指向
ListNode* reverseList2(ListNode* head) {
if (head == nullptr) return nullptr;
if (head->next == nullptr) return head;
ListNode* last = reverseList2(head->next); // 递归调用，翻转第二个节点开始往后的链表
head->next->next = head; // 翻转头节点与第二个节点的指向
head->next = nullptr; // 此时的 head 节点为尾节点，next 需要指向 NULL
return last;
}
// 递归 和双指针法是一样的逻辑
ListNode* reverse(ListNode* pre, ListNode* cur) {
if (cur == nullptr) return pre;
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur, tmp);
}
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
};
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
初始时，cur指向虚拟头结点，然后进行如下三步：
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0, head);
ListNode* prev = dummyHead;
while (prev->next != nullptr && prev->next->next != nullptr) {
ListNode* cur = prev->next;
ListNode* tmp = cur->next;
prev->next = tmp;
cur->next = tmp->next;
tmp->next = cur;
prev = cur;
}
return dummyHead->next;
}
};
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？
双指针：快指针比慢指针先走 n 步。
class Solution {
public:
// 双指针
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0, head);
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
while (fast->next != nullptr) { // 找到节点
slow = slow->next;
fast = fast->next;
} // 使slow指向前一个节点
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dummyHead->next;
}
};
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。
双指针
class Solution {
public:
// a+c+b(走对方的路)和b+c+a(走对方的路)，如果相交，两人走的是路长是一致的，会同时达到点。
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
ListNode* curA = headA;
ListNode* curB = headB;
while (curA != curB) { // 要么相遇即节点相等，要么都为空
curA = (curA != nullptr) ? curA->next : headB;
curB = (curB != nullptr) ? curB->next : headA;
}
return curA;
}
};
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
主要考察两知识点：1. 判断链表是否环 2. 如果有环，如何找到这个环的入口.
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while p != q:
p = p.next
q = q.next
return p
return None
PS
以上题解大多来自【代码随想录】，在此基础上做了一定总结，并附带一些自己的理解。
随缘更新，有错误请指出！
END