LeetCode每日一刷 — 手撕单链表习题（1）
目录
1、移除链表元素
- 链接直达：
- 题目：
- 思路：
此题要综合考虑多种情况，常规情况就如同示例1，有多个节点，并且val不连续，但是非常规呢？当val连续呢？当头部就是val呢？所以要分类讨论
常规情况：
需要定义两个指针prev和cur，cur指向第一个数据，prev指向cur的前一个。依次遍历cur指向的数据是否为val，若是，则把prev的下一个节点指向cur的下一个节点上，cur=cur->next，prev跟着cur一起走，直到cur走到NULL
连续val：
当我们仔细观察下，不难发现，在常规情况下是可以解决连续val的，但是头部val就不可了
头部val：
此时除了刚才定义的两个指针prev和cur外，还要有个head指向头部，当头部是val时，将cur指向下一个位置，head跟着一起动，直到cur指向的数据不为val时，将head赋给prev。此时剩余的就按常规处理即可。
- 代码如下：
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur=head; struct ListNode*prev=NULL; while(cur) { if(cur->val!=val) { prev=cur; cur=cur->next; } else { struct ListNode*next=cur->next; if(prev==NULL) { free(cur); cur=next; head=next; } else { prev->next=cur->next; free(cur); cur=prev->next; } } } return head; }
2、反转链表
- 链接直达：
- 题目：
- 思路：
法一：三指针翻转方向
定义三个指针n1，n2，n3分别用来指向NULL，第一个数据，第二个数据。让n2的next指向n1，把n2赋给n1，再把n3赋给n2，再执行n3=n3->next的操作，接下来重复上述操作，直到n2指向空即可。但是要注意，要先判断该链表是否为NULL，如果是，则返回NULL，此外，还要保证当n3为空时就不要动了，直接把n3赋给n2即可。
- 代码如下：
struct ListNode* reverseList(struct ListNode* head){ if(head==NULL) { return NULL; } struct ListNode*n1=NULL; struct ListNode*n2=head; struct ListNode*n3=n2->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) { n3=n3->next; } } return n1; }法二：头插
此法就需要再创建一个链表了，创建一个新的头部newhead指向NULL，再定义一个指针cur指向原链表第一个数据，注意还得定义一个指针next指向cur的下一个节点。遍历原链表，把节点取下来头插到newhead所在的链表。每次更新newhead赋给cur，如图所示：
- 代码如下：
struct ListNode* reverseList(struct ListNode* head){ if(head==NULL) { return NULL; } struct ListNode*cur=head; struct ListNode*next=cur->next; struct ListNode*newhead=NULL; while(cur) { cur->next=newhead; newhead=cur; cur=next; if(next) { next=next->next; } } return newhead; }
3、链表的中间节点
- 链接直达：
- 题目：
- 思路：
快慢指针
这道题要注意奇偶数，如果为奇数，如示例1，那么中间节点值就是3，反之偶数如示例2，返回第二个中间节点。此题我们定义两个指针slow和fast都指向第一个数据的位置，区别在于让slow一次走1步，fast一次走2步。当fast走到尾指针时，slow就是中间节点
- 代码如下：
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*slow=head; struct ListNode*fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; } return slow; }
4、链表中倒数第k个节点
- 链接直达：
- 题目：
- 思路：
快慢指针
定义两个指针slow和fast，让fast先走k步，再让slow和fast同时走，当fast走到尾部时，slow就是倒数第k个，因为这样的话slow和fast的差距始终是k个，当fast走到空时结束。此题同样可以走k-1步，不过当fast走到尾部时结束，也就是fast的下一个节点指向空时结束，都一样。先拿走k步举例，如图所示：
- 代码如下：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode*fast=pListHead; struct ListNode*slow=pListHead; while(k--) { //if判断，防止k大于链表的长度 if(fast==NULL) return NULL; fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }
5、合并两个有序链表
- 链接直达：
- 题目：
- 思路：
法一：归并（取小的尾插）--- 带头节点
假设新链表的头叫head并指向NULL，还需要定义一个指针tail来方便后续的找尾，依次比较list1和list2节点的值，把小的放到新链表head上，并更新tail，再把list1或list2更新一下。当list1和list2两个链表中一个走到空时，直接把剩下的链表所有剩下的元素拷进去即可
- 代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ //检查list1或list2一开始就为NULL的情况 if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } struct ListNode*head=NULL; struct ListNode*tail=head; while(list1&&list2) { if(list1->val<list2->val) { if(tail==NULL) { head=tail=list1; } else { tail->next=list1; tail=list1; } list1=list1->next; } else { if(tail==NULL) { head=tail=list2; } else { tail->next=list2; tail=list2; } list2=list2->next; } } //当list1和list2其中一个走到空的情况 if(list1==NULL) { tail->next=list2; } else { tail->next=list1; } return head; }法二：哨兵位的头节点
解释下带头节点：
比如说同样一个链表存1，2，3。不带头节点只有这三个节点，head指向1。而带头节点的同样存3个值，不过有4个节点，head指向头部这个节点，这个节点不存储有效数据
带头结点有如下好处，不用判断head和tail是否为空了，也不用判断list1和list2是否为空了，会方便不少。和上述思路一样，取小的下来尾插，直接链接到tail后面即可。但是要注意返回的时候要返回head的next，因为题目给的链表是不带头的，而head本身指向的就是那个头，所以要返回下一个。
- 代码如下：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode* head = NULL, * tail = NULL; head = tail = (struct ListNode*)malloc(sizeof(struct ListNode)); head->next = NULL; while (list1 && list2) { if (list1->val < list2->val) { tail->next = list1; tail = list1; list1 = list1->next; } else { tail->next = list2; tail = list2; list2 = list2->next; } } //当list1和list2其中一个走到空的情况 if (list1 == NULL) { tail->next = list2; } else { tail->next = list1; } struct ListNode* list = head->next; free(head); head = NULL return list; }
6、链表分割
- 链接直达：
- 题目：
- 思路：
定义两个链表lesshead和greaterhead。遍历原链表，把 < x 的插入到链表1，把 > x 的插入到链表2，最后再把链表1和链表2链接起来。在定义两个尾指针以跟进链表1和2新增元素
- 代码如下：
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail; lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); lessTail->next = greaterTail->next = NULL; struct ListNode* cur = pHead; while (cur) { if (cur->val < x) { lessTail->next = cur; lessTail = lessTail->next; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } //合并 lessTail->next = greaterHead->next; greaterTail->next = NULL; struct ListNode* list = lessHead->next; free(lessHead); free(greaterHead); return list; } };