链表OJ
- 1. 头插或三指针翻转法
- 2. LeetCode203题---移除链表元素
- 3. 快慢指针法及其变形
- 4. 找到长链表然后走差值步，然同时走
- 5. 创造带哨兵位的头结点和尾结点法
- 6. LeetCode21题---合并两个有序链表
- 8. LeetCode138题---复制带随机指针的链表
- 9. LeetCode147题---对链表进行插入排序
- 10. 删除链表中重复的元素
1. 头插或三指针翻转法
1.1 LeetCode206题—反转链表
链接: https://leetcode-cn.com/problems/reverse-linked-list/
①首选方法：头插法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* newHead = nullptr;
ListNode* cur = head;
while(cur != nullptr)
{
ListNode* next = cur->next;
cur->next = newHead;
newHead = cur;
cur = next;
}
return newHead;
}
};
②三指针翻转法
class Solution {
public:
//翻转链表还有一个经典的解法就是三指针翻转
ListNode* reverseList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* n1 = nullptr,*n2 = head,*n3= head->next;
while(n2 != nullptr)
{
n2->next = n1;
n1 = n2;
n2 = n3;
//因为n3是最先出去的，如果解引用就会出现崩的情况
if(n3 != nullptr)
{
n3 = n3->next;
}
}
return n1;
}
};
2. LeetCode203题—移除链表元素
链接: https://leetcode-cn.com/problems/remove-linked-list-elements/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* prev = nullptr,*cur = head;
while(cur)
{
if(cur->val == val)
{
//此时还要考虑不会不是一开始就是相同的
if(cur == head)
{
head = cur->next;
delete cur;
cur = head;
}
else
{
prev->next = cur->next;
delete cur;
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
};
3. 快慢指针法及其变形
3.1 LeetCode876题—链表的中间结点
链接: https://leetcode-cn.com/problems/middle-of-the-linked-list/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
//这道题提示给定了链表的节点数介于1——100之间，所以链表不可能为nullptr
ListNode* slow = head,*fast = head;
//1 2 3 4 如果是偶数个判断的条件就是fast != nullptr
//1 2 3 4 5 如果是奇数个判断条件就是fast->next != nullptr
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
3.2 剑指offer22题—链表中倒数第k个结点
链接:https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
题解：先让快指针走k步，然后快慢指针在一起走，当快指针都到空的时候，慢指针刚好在倒数第k个结点的位置
class Solution {
public:
//这道题我没有考虑到K的值是大于链表的长度的，为什么还过了
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode* slow = head,*fast = head;
//这也就是我上面所考虑到的问题，如果K的值大于了你链表的长度呢？
while(fast && k!=0)
{
//这里是有可能空指针访问的，越界应该要报错的，但是LeetCode这里处理不好
fast = fast->next;
k--;
}
while(fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
3.3 剑指offer27题—链表的回文结构
链接:https://leetcode-cn.com/problems/aMhZSa/
题解：使用到了快慢指针用来找到中间结点，然后使用翻转链表，在比较两个链表的结点是否都相同
class Solution {
public:
//首先找到中间节点，然后在对后半部分进行逆置，在对比前半部分和后半部分是否相同
bool isPalindrome(ListNode* head) {
ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
//现在我们就假设设个链表是一个偶数
//那么根据实例一，就可以知道此事slow所指向的位置就是下中位数的3，然后我们以这个结点进行翻转
ListNode* newNode = nullptr;
ListNode* cur = slow;
while(cur)
{
ListNode* next = cur->next;
cur->next = newNode;
newNode = cur;
cur = next;
}
//走到这里newNode就是翻转过后新链表的头结点
while(newNode)
{
if(newNode->val != head->val)
return false;
head = head->next;
newNode = newNode->next;
}
return true;
}
};
3.4 LeetCode141题—环形链表I
链接:https://leetcode-cn.com/problems/linked-list-cycle/
题解：为什么快指针走的是慢指针的两倍，走三倍或者4倍不行吗？
答案是不行，因为只有快指针是慢指针的两倍时候，假设他们都进入环里以后开始相差的距离是x，那么他们分别每走一步，距离就缩短为x-1,x-2…0，一定会相遇，如果是3倍或者4倍那么在有些情况下就有可能会错过
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}
};
3.5 LeetCode142题—环形链表II
链接:https://leetcode-cn.com/problems/linked-list-cycle-ii/
题解：这个是需要经过验证的，2(L+X) = L + NC+X,得到L=NC-X，刚好从他们在环里相遇的点开始走和头结点开始走到第一个相遇的点的距离都是L
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head,*fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
break;
}
//要排除掉没有相遇的情况，确保一定是break出来的
if(fast == nullptr || fast->next == nullptr)
return nullptr;
ListNode* meet = fast;
while(head!=fast)
{
head = head->next;
fast = fast->next;
}
return fast;
}
};
4. 找到长链表然后走差值步，然同时走
4.1 LeetCode160题—相交链表
链接:https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
题解：让长链表先走他们的差距步，这样就保证了两个链表的长度是一样的了，然后他们在同时走，那么相遇的结点就是相交结点
class Solution {
public:
//这道题找的是相交的结点，不是值
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int la = 0,lb = 0;
//一般不要轻易改变head，使用一个变量来替换head
ListNode* curA = headA;
while(curA)
{
la++;
curA = curA->next;
}
ListNode* curB = headB;
while(curB)
{
lb++;
curB = curB->next;
}
ListNode* longList = headA,*shortList = headB;
if(la < lb)
{
longList = headB;
shortList = headA;
}
int gap = abs(la-lb);
while(gap)
{
longList = longList->next;
gap--;
}
//此时走到这里就说明了他们两个此时是一样长的
while(longList)
{
if(longList!= shortList)
{
longList = longList->next;
shortList = shortList->next;
}
else
{
return longList;
}
}
return nullptr;
}
};
5. 创造带哨兵位的头结点和尾结点法
5.1 牛客网—链表分割
链接: link.
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
//带哨兵位的头结点是不保存任何的有效数值的,并且对这个头结点里面存储的数据进行初始化
ListNode* lesserHead,*lesserTail;
ListNode* greaterHead,*greaterTail;
lesserHead = new ListNode(1);
greaterHead= new ListNode(1);
lesserTail = lesserHead;
greaterTail = greaterHead;
lesserHead->next = greaterHead->next = nullptr; //对头结点进行初始化
ListNode* cur = pHead;
while(cur)
{
if(cur->val < x)
{
lesserTail->next = cur;
lesserTail = lesserTail->next;
}
else
{
greaterTail->next = cur;
greaterTail = greaterTail->next;
}
cur = cur->next;
}
//因为有可能造成回环
//例如题目如果是 1 9 3 5 6 7 x=4那么没有问题
//如果是1 9 3 5 6 7 2 x=4 那么就出现链表回环问题了
greaterTail->next = nullptr;
lesserTail->next = greaterHead->next;
//这一步是为了要释放到所开辟的两个头结点，所以要保存一下
ListNode* list = lesserHead->next;
delete lesserHead;
delete greaterHead;
return list;
}
};
6. LeetCode21题—合并两个有序链表
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr && l2 == nullptr)
return nullptr;
if(l1 == nullptr)
return l2;
if(l2 == nullptr)
return l1;
//走到这里就说明l1和l2都不为空
//定义一个头结点和尾结点
struct ListNode* head = nullptr,*tail = nullptr;
if(l1->val <= l2->val)
{
head = tail = l1;
l1 = l1->next;
}
else
{
head = tail = l2;
l2 = l2->next;
}
//此时就是取较小的结点值进行尾插就可以
while(l1 && l2)
{
if(l1->val <= l2->val)
{
tail->next = l1;
l1 = l1->next;
}
else
{
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
if(l1)
{
tail->next = l1;
}
else
{
tail->next = l2;
}
return head;
}
};
8. LeetCode138题—复制带随机指针的链表
链接:https://leetcode-cn.com/problems/copy-list-with-random-pointer/
第一种方法：拷贝出的结点链接在原结点后面，然后在修改拷贝结点里面next和random，最后还原原链表的样子
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr)
return nullptr;
Node* cur = head;
while(cur)
{
//创建一个拷贝结点
Node* copy = new Node(cur->val);
copy->next = nullptr;
copy->random = nullptr;
Node* next = cur->next;
//然后修改链接的关系
cur->next = copy;
copy->next = next;
cur = next;
}
//此时就给每个结点都复制了一个相同的结点，但是里面的random关系却还没有改变
cur = head;
while(cur)
{
Node* copy = cur->next;
if(cur->random)
{
copy->random = cur->random->next;
}
else
{
copy->random = nullptr;
}
cur = copy->next;
}
//上面就把所有的random关系都修改完了，剩下的就是恢复原来的链表结构了
cur = head;
Node* newHead = cur->next;
while(cur)
{
Node* copy = cur->next;
Node* next = copy->next;
cur->next = next;
if(next)
{
copy->next = next->next;
}
else
{
copy->next = nullptr;
}
cur = next;
}
return newHead;
}
};
**推荐方法（应为比第一题写的要少很多）**第二种方法：Hash映射—构成原结点和结点之间的映射关系,第一次变量就是为了侯建映射，第二次遍历则是为了修改拷贝出来链表中结点的next和random
class Solution {
public:
//第二种方法就是使用Hash，但是要想清楚，到底是什么和什么只要要构成映射，才能够解出来这道题
//从题解上来看是，构建原结点和新节点之间的映射关系
Node* copyRandomList(Node* head) {
if(head == nullptr)
return nullptr;
unordered_map<Node*,Node*> HashMap;
Node* cur = head;
while(cur)
{
HashMap[cur] = new Node(cur->val);
cur = cur->next;
}
cur = head;
Node* copyHead = HashMap[cur];
while(cur)
{
HashMap[cur]->next = HashMap[cur->next];
HashMap[cur]->random = HashMap[cur->random];
cur = cur->next;
}
return copyHead;
}
};
9. LeetCode147题—对链表进行插入排序
链接:https://leetcode-cn.com/problems/insertion-sort-list/
题解：就是插入排序的思想，把第一个当做有顺序的，然后拿着剩下的结点去插入，当问题解不下去的时候，就把最简单的想写了，然后剩下的就自然出来了，比如说先把头插的方法写掉，剩下的就是中间插入或者尾插了
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
//这两步就相当于取了第一个结点作为排序的头
ListNode* sortHead = head;
//剩下的就是拿从第二个结点到结束的结点进行插入
ListNode* cur = head->next;
sortHead->next = nullptr;
while(cur)
{
ListNode* next = cur->next;
//拿着结点去插入，但是这里又三种可能1.cur->val值小于等sortHead，头插
//2.cur->val值大于sortHead->val，那就往后走，此时有可能是尾插也有可能是中间插入
if(cur->val <= sortHead->val)
{
//头插
cur->next = sortHead;
sortHead = cur;
}
else
{
//中间插入或者尾插,前面已经排除了头插的可能
ListNode* sortprev = sortHead,*sortcur = sortprev->next;
while(sortcur)
{
if(cur->val>sortcur->val)
{
sortprev = sortcur;
sortcur = sortcur->next;
}
else
{
sortprev->next = cur;
cur->next = sortcur;
break;
}
}
if(sortcur == nullptr)
{
sortprev->next = cur;
cur->next = nullptr;
}
}
cur = next;
}
return sortHead;
}
};
10. 删除链表中重复的元素
10.1 LeetCode83题—删除链表中重复的结点I
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == nullptr || head->next==nullptr)
return head;
ListNode* cur = head;
while(cur->next)
{
if(cur->val == cur->next->val)
{
cur->next = cur->next->next;
}
else
{
cur = cur->next;
}
}
return head;
}
};
10.2 LeetCode82题—删除链表中重复的结点II
链接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
题解：先把正常的写掉，然后在考虑不正常的情况，比如头部就有相同的，尾部有相同的两种情况在进行考虑
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == nullptr || head->next == nullptr)
return head;
ListNode* prev = nullptr,*cur = head,*next = cur->next;
while(next)
{
//如果实在想不出来应该怎么写的时候，应该就想把正常的谢安，在考虑不正常的情况
if(cur->val != next->val)
{
prev = cur;
cur = next;
next = next->next;
}
else
{
//头就开始相等
while(next &&cur->val == next->val)
{
next = next->next;
}
if(prev)
{
prev->next = next;
}
else
{
head = next;
}
//尾部开始相等
//跳出上面的循环有两种可能，一种就是cur->val != next->val 包含了头不正常和中间不正常
//还有一种情况就是尾不正常 也就是跳出循环的第二个可能
//为了避免内存泄漏，要把结点释放掉
while(cur!= next)
{
ListNode* Node = cur;
cur = cur->next;
delete Node;
}
//因为尾部相同的时候，是由可能cur指向了next的空，然后在解引用就会崩了
if(next)
next = cur->next;
}
}
return head;
}
};