链表入门（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指向5head->next->next=head;//head->next指向反转链表的最后一个，此句把自己接到后面head->next=nullptr;//接到的是尾部，所以next为nullptrreturn 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;//尾部置nullreturn lower->next;}
};