LC203 移除链表元素
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head) return head;
// 单指针，提前预判下个节点是不是目标值，之后做跨越连接，删除
// 注意：这里不能这么写 VHeader = head;
// 针对这个测试用例[7,7,7,7], val = 7
ListNode* VHeader = new ListNode(-1,head);
ListNode* cur = VHeader;
ListNode* tem = nullptr;
while (cur->next)
{
if (cur->next->val == val)
{
tem = cur->next;
cur->next = cur->next->next;
delete tem;
}
else cur = cur->next;
}
// 针对这个测试用例[7,7,7,7], val = 7
head = VHeader->next;
delete VHeader;
return head;
}
};
LC707 设计链表
这道题描述给人挖了个坑，需要仔细看题目。
get(int index)/deleteAtIndex(int index) 下标从0开始数到第index个
addAtIndex(int index, int val) 下标从1开始数到第index个
class MyLinkedList {
public:
struct LinkNode
{
int val = -1;
LinkNode* next = nullptr;
LinkNode(int v) : val(v) {}
};
MyLinkedList() {
Vhader = new LinkNode(-1);
}
// index 按数组下标 0 ..k.. n 的第 k个
int get(int index) {
if (!Vhader->next) return -1;
else if (index >= _size) return -1;
tem = Vhader->next;
while (index--)
tem = tem->next;
return tem->val;
}
// index 按日常计数顺序 1 ..k.. n 的第 k个(英国从0...n开始数例外 - 雾 -)
void addAtIndex(int index, int val) {
if (index > _size) return ;
tem = Vhader;
LinkNode* old = nullptr;
while (index--)
tem = tem->next;
old = tem->next;
tem->next = new LinkNode(val);
tem->next->next = old;
_size++;
}
// 同 index 按数组下标 0 ..k.. n 的第 k个
void deleteAtIndex(int index) {
if (index >= _size) return;
tem = Vhader;
LinkNode* old = nullptr;
while (index--)
tem = tem->next;
old = tem->next->next;
delete tem->next;
tem->next = old;
--_size;
}
void addAtHead(int val) {
tem = Vhader->next;
Vhader->next = new LinkNode(val);
Vhader->next->next = tem;
_size++;
}
void addAtTail(int val) {
tem = Vhader;
while (tem->next) tem = tem->next;
tem->next = new LinkNode(val);
_size++;
}
private:
LinkNode* Vhader = nullptr;
LinkNode* tem = nullptr;
int _size = 0;
};
LC206 反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* cur = nullptr;
ListNode* pre = head;
ListNode* tem = nullptr;
while(pre)
{
tem = pre->next;
pre->next = cur;
cur = pre;
pre = tem; // 注意这里
}
return cur;
}
};
LC24 两两交换链表中的节点
脑筋急转弯，不要做两节点得指针指向，直接互换节点中的值，这样写立马不抽象...
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* VHead = new ListNode(-1,head);
ListNode* cur = VHead;
int tem;
// 其实不用交换指针，交换节点中的值就好(脑筋急转弯)，交换两节点指针指向操作繁琐
while (cur->next && cur->next->next)
{
tem = cur->next->val; //备份下个节点得值
cur->next->val = cur->next->next->val; // 当前节点得下个节点的值覆盖 为下下个结点的值
cur->next->next->val = tem;
cur = cur->next->next; // 跳到交换值得第二节点，下次回做回直接看下一个节点和下下个节点，并交换
}
return head;
}
};LC19 删除链表的倒数第N个节点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* VHead = new ListNode(-1,head);
ListNode* cur = VHead;
ListNode* pre = head;
while(n -- && pre) pre = pre->next;
while(pre)
{
pre = pre->next;
cur = cur->next;
}
ListNode* tem = cur->next;
cur->next = cur->next->next;
delete tem;
return VHead->next;
}
};
LC 链表相交
面试题 02.07. 链表相交 - 力扣（LeetCode）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 第一次遍历得到两链表长度(不管是否相交)
// 重置两链表遍历指针,计算出两链表相差几个节点数(也就是长的比短的多几个节点) - delta
// 让长的先走delta步(delta = |lenA - lenB|)
// 之后两指针同时向前移动，相交则回地址相同(curA == curB) 返回ture,否则其中一个遍历指针遍历到末尾则认为没有相交点.
if (!headA || !headB) return nullptr;
int lenA = 1, lenB = 1;
ListNode* curA = headA;
ListNode* curB = headB;
while (curA || curB)
{
if (curA){
curA = curA->next;
lenA ++;
}
if (curB)
{
curB = curB->next;
lenB ++;
}
}
curA = headA;
curB = headB;
// ListNode*& 指针引用， C++ 11新特性，但是这里*和& 必须写一起，且 必须和类型名紧挨 : ListNode*&
auto f = [](ListNode*& curA, ListNode*& curB, int delta) -> ListNode* /* c++ 11 匿名函数返回值 */ {
while(delta --) curA = curA->next;
while(curA && curB)
{
if (curA == curB) return curA;
else
{
curA = curA->next;
curB = curB->next;
}
}
return nullptr;
};
return lenA > lenB ? f(curA,curB,lenA - lenB) : f(curB,curA,lenB - lenA);
}
};
LC142 环形链表II
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head,*fast = head;
// 快慢指针，快指针比慢指针多走一步，如果有环，两指针总会相遇
// 相遇后快指针重置从链表头开始追慢指针，相遇得的地方就是环入口，证明、图解网上搜，图太长...有理论证明的。(定律黎嘅)
while(fast)
{
slow = slow->next;
if(!fast->next) return nullptr;
else fast = fast->next->next;
if (slow == fast)
{
fast = head;
while(slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return fast;
}
}
return nullptr;
}
};