链表入门（LeetCode题目）
链表的题目我们经常是有思路但是实现起来总有些小问题，所以是准备笔试应多加练习的一类题
206. 反转链表
这道题我们可以新开链表来存，但是如果面试中有这道题，面试官让你优化又该如何呢？所以我们采用前后指针方法来解决
/**
* 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) {
ListNode *pre=nullptr;//前指针
ListNode *next=nullptr;//后指针
while(head)
{
next=head->next;//先把该节点的下一个结点存下来
head->next=pre;//修改该结点的下一个结点为前一结点
pre=head;//前一结点移到当前位置
head=next;//当前结点往后移动
}
return pre;//最后pre保存新的头结点，另两个结点为空
}
};同时，本题还有递归解法，非常巧妙
/**
* 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==nullptr||head->next==nullptr)
return head;//第一个条件只是判断初始链表为空的情况
ListNode *cur=reverseList(head->next);
//以[1,2,3,4,5]为例，现在head指向4，cur指向5
head->next->next=head;
//head->next指向反转链表的最后一个，此句把自己接到后面
head->next=nullptr;
//接到的是尾部，所以next为nullptr
return cur;
}
};附录：反转双链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* next = nullptr;
while (head ) {
next = head->next;
head->next = pre;
head->last = next;
pre = head;
head = next;
}
return pre;
}21. 合并两个有序链表
这里我们使用一个哨兵结点方便后续书写
/**
* 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode head{};//哨兵结点
ListNode* cur=&head;//指向哨兵结点
while(list1&&list2)
{
if(list1->val<list2->val)
{
cur->next=list1;//指向小的
list1=list1->next;//链表指针移动
}
else
{
cur->next=list2;
list2=list2->next;
}
cur=cur->next;//合并链表指针移动到尾结点
}
cur->next=list1?list1:list2;//哪个有剩余就加上
return head.next;//返回头节点
}
};2. 两数相加
这道题依然使用哨兵结点，便于处理
/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
int up = 0;//算进位和余数
ListNode* head = new ListNode;//哨兵结点
ListNode* cur = head;//指针指向哨兵结点
while (l1 || l2 || up) {
//只要链表没遍历完，或进位里仍有数
int val1 = l1 ? l1->val : 0;//链表不为空取值
int val2 = l2 ? l2->val : 0;
up += val1 + val2;//之前进上的位与当前相加
ListNode* t = new ListNode(up % 10);//新建结点存答案
up /= 10;//应进位多少
cur->next = t;//接到答案链表后面
cur = cur->next;//链表指针移动
if (l1)
l1 = l1->next; //链表不为空移动
if (l2)
l2 = l2->next;
}
return head->next;//返回哨兵结点保存的头结点
}
};86. 分隔链表
这个题如果我们扫描然后把小的放前面用到的指针比较多，较麻烦。
所以我们用两个链表分别存储，再最后合并即可。
/**
* 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* partition(ListNode* head, int x) {
//开两个链表分别存储，最后合并链表即可
ListNode* lower = new ListNode(0);//<x的结点
ListNode* upper = new ListNode(0);//>=x的结点
//两个都是哨兵结点
ListNode *p1 = lower, *p2 = upper;
//指针分别指向两链表，便于后续增加结点
if (!head)
return head;//为空直接返回
while (head) {//一直遍历
if (head->val < x) {//小于接到lower链表
p1->next = head;
p1 = p1->next;
head = head->next;
} else {
p2->next = head;//大于等于接到upper链表
p2 = p2->next;
head = head->next;
}
}
p1->next = upper->next;//upper接到lower后面
p2->next = nullptr;//尾部置null
return lower->next;
}
};原文地址：https://blog.csdn.net/qq_74924951/article/details/142533377
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！