题目1 203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
- 列表中的节点数目在范围
[0, 104]内 1 <= Node.val <= 500 <= val <= 50
思路
- 使用不带虚拟头的链表进行操作，这样做就需要分为两部分去进行判断，第一部分是链表头到不是val数值的节点，第二部分是不是val数值的节点到链表尾部。因为整个链表要遍历一遍所以时间复杂度为O(n)，n为链表长度。
代码
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode * tmpNode;
while(head!= nullptr && head->val == val)
{
tmpNode = head;
head = head->next;
delete tmpNode;
}
if(head == nullptr) return head;
ListNode * preNode = head;
tmpNode = preNode->next;
while(tmpNode != nullptr)
{
if(tmpNode->val == val)
{
preNode->next = tmpNode->next;
delete tmpNode;
tmpNode = preNode->next;
}
else
{
preNode = preNode->next;
tmpNode = tmpNode->next;
}
}
return head;
}
};
- 使用虚拟头
使用虚拟头节点后，将虚拟头节点的next指针指向头节点并让头节点指针暂时指向虚拟头，之后就只需要按顺序判断节点是否满足条件并操作就行了，在最后要注意让头节点指针指向虚拟头节点的next指针。时间复杂度也是O(n)。
代码
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* tmpNode = new ListNode(0, head);
head = tmpNode;
while(tmpNode->next != nullptr)
{
if(tmpNode->next->val == val)
{
ListNode* cur = tmpNode->next;
tmpNode->next = cur->next;
delete cur;
}
else
{
tmpNode = tmpNode->next;
}
}
tmpNode = head;
head = head->next;
delete tmpNode;
return head;
}
};
题目2 707. 设计链表
你可以选择使用单链表或者双链表，设计并实现自己的链表。
单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。
实现 MyLinkedList 类：
MyLinkedList()初始化MyLinkedList对象。int get(int index)获取链表中下标为index的节点的值。如果下标无效，则返回-1。void addAtHead(int val)将一个值为val的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。void addAtTail(int val)将一个值为val的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)将一个值为val的节点插入到链表中下标为index的节点之前。如果index等于链表的长度，那么该节点会被追加到链表的末尾。如果index比长度更大，该节点将 不会插入 到链表中。void deleteAtIndex(int index)如果下标有效，则删除链表中下标为index的节点。
示例：
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]
解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3
myLinkedList.get(1); // 返回 2
myLinkedList.deleteAtIndex(1); // 现在，链表变为 1->3
myLinkedList.get(1); // 返回 3
思路
这道题就是考察链表的基本功，可以用单链表或者双链表的形式去做，我使用的是双链表。要注意的就是函数里面开头判断后要及时返回及index计数问题。
代码
//双链表节点类
struct Node
{
Node* prev;
Node* next;
int val;
Node(int val = 0, Node* Prev = nullptr, Node* Next = nullptr):val(val), prev(Prev), next(Next)
{}
};
class MyLinkedList {
public:
MyLinkedList() {
head = new Node;
head->next = head;
head->prev = head;
size = 0;
}
int get(int index) {
if(index >= size) return -1;
Node * tmp = head->next;
while(index--)
{
tmp = tmp->next;
}
return tmp->val;
}
void addAtHead(int val) {
size++;
Node* tmpNode = new Node(val, head, head->next);
tmpNode->prev->next = tmpNode;
tmpNode->next->prev = tmpNode;
}
void addAtTail(int val) {
size++;
Node* tmpNode = new Node(val, head->prev, head);
tmpNode->prev->next = tmpNode;
tmpNode->next->prev = tmpNode;
}
void addAtIndex(int index, int val) {
if(index > size) return;
if(index == size)
{
addAtTail(val);
return;
}
Node*tmpNode = head->next;
while(index--)
{
tmpNode = tmpNode->next;
}
Node* newNode = new Node(val, tmpNode->prev, tmpNode);
newNode->next->prev = newNode;
newNode->prev->next = newNode;
size++;
}
void deleteAtIndex(int index) {
//index超过链表大小直接返回
if(index >= size) return;
Node* tmpNode = head->next;
while(index--)
{
tmpNode = tmpNode->next;
}
tmpNode->prev->next = tmpNode->next;
tmpNode->next->prev = tmpNode->prev;
delete tmpNode;
size--;
}
private:
Node* head;
//size用于记录链表大小
int size;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
题目3 206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目范围是
[0, 5000] -5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
思路
迭代法
迭代法就是正常的遍历链表，并在遍历时反转节点的next指针指向就行了，要注意的就是头节点要指向空。
代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr)
{
return head;
}
ListNode* tmpNode = head->next;
head->next = nullptr;
while(tmpNode != nullptr)
{
ListNode* next = tmpNode->next;
tmpNode->next = head;
head = tmpNode;
tmpNode = next;
}
return head;
}
};
递归法
这个就是和迭代法类似，将每次迭代的反转操作分为一次递归，这样分而治之最终得出反转链表，需要注意的就是递归终止的结束条件。
代码
class Solution {
public:
ListNode* reverse(ListNode* lft, ListNode* rht)
{
if(rht == nullptr)
{
return lft;
}
ListNode* tmp = rht->next;
rht->next = lft;
return reverse(rht, tmp);
}
ListNode* reverseList(ListNode* head) {
if(head == nullptr)
{
return head;
}
return reverse(nullptr, head);
}
};