一、移除链表元素
移除链表中值为val的元素,并返回新的头节点
思路:
题目上这样说,我们就可以创建一个新的链表,将值不为val的节点,尾插到新的链表当中,最后返回新链表的头节点。
typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { if(head==NULL) { return NULL; } ListNode* newhead = (ListNode*)malloc(sizeof(ListNode)); ListNode* ptail = head; ListNode* pcur = newhead; while (ptail) { if (ptail->val != val) { pcur->next = ptail; pcur = pcur->next; } ptail = ptail->next; } pcur->next=NULL; ListNode* ret = newhead->next; free(newhead); newhead = NULL; return ret; }
当然,这个题还有其他思路。
二、反转链表
将链表反转,并返回反转后的链表的头节点
思路:
创建三个指针变量,l1,l2,l3(指针初始指向如下图),遍历链表,先让l3=l2->next;再将l2的next指针指向l2;再l1指向l2,l2指向l3(l2下一个节点);直到遍历结束,结束条件为(l2等于NULL)此时l1指向的就是反转后的链表的头节点。
根据题目给的示例来分析
遍历数组,循环进行一次
l2不等于NULL循环继续
l2不等于NULL循环继续
l2不等于NULL循环继续
l2仍然不等于NULL,循环继续
到这里,l2已经遍历到了NULL,循环结束,此时l1指向的就是反转后链表的头节点,直接返回即可。
typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* l1,*l2,*l3; l1=NULL; l2=head; while(l2) { l3=l2->next; l2->next=l1; l1=l2; l2=l3; } return l1; }
三、链表的中间节点
看到这个题,本人一开始的想法是:遍历一遍链表,记录链表的节点个数,然后再遍历一次链表,寻找链表的中间节点;这样实现非常麻烦,现在使用一种新的方法来解决这个问题
思路:快慢指针
定义两个快慢指针,fast和slow刚开始都指向链表的头节点,fast每次向前走两个节点,而slow指针每次向前走一个节点;最后当fast指针或者fast的next指针为NULL遍历结束;此时slow指向的就是链表的中间节点。
根据题所给的示例分析:
链表个数为奇数
fast=fsat->next->next;
slow=slow->next;
遍历到这里,fast的next指针为空,循环结束;此时slow指向的就是链表的中间节点。
链表的节点数为偶数
fast=fsat->next->next;
slow=slow->next;
循环到这里,fast为空,循环结束,此时slow指向的节点就是链表的中间节点。
typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { if(head==NULL) { return NULL; } ListNode* fast=head; ListNode* slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } return slow; }
四、合并两个有序链表
合并两个有序链表,这里创建一个新的链表,将两个链表中较小小的数据依次尾插到新链表中,最后返回新链表的头节点即可。
注意:这里需要注意,初始的两个链表可能为空,这里需要进判断,如果list1为空,就返回list1;如果list2为空,就返回list1。
根据题目示例分析
比较l1和l2指向的节点的值大小,l1->val=l2->val(l1的不小于l2的),将l2指向节点尾插到新链表
此时,l1->val < l2->val,将l1指向的节点尾插到新链表
此时,l1->val < l2->val,将l1指向的节点尾插到新链表
比较l1和l2指向的节点的值大小,l2->val < l1->val,将l2指向节点尾插到新链表
比较l1和l2指向的节点的值大小,l1->val=l2->val(l1的不小于l2的),将l2指向节点尾插到新链表
l2为空,循环结束,这里l1的节点还没全部插到新链表中,这里直接 ptail->next=l1;即可。
注:这里使用动态内存来给newhead开辟空间,记得将其释放掉,养成好习惯。
typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } ListNode* l1=list1; ListNode* l2=list2; ListNode* newhead=(ListNode*)malloc(sizeof(ListNode)); ListNode* ptail=newhead; while(l1 && l2) { if(l1->val<l2->val) { ptail->next=l1; l1=l1->next; } else { ptail->next=l2; l2=l2->next; } ptail=ptail->next; } if(l1) { ptail->next=l1; } if(l2) { ptail->next=l2; } ListNode* ret=newhead->next; free(newhead); newhead=NULL; return ret; }
五、链表分割
将链表小于x的节点排在其余节点之前,不能改变原来顺序,最后返回排序好的链表的头指针。
思路:
创建两个链表,一个链表l1,存放值小于val的节点;另一个链表l2,存放值大于等于val的节点。最后将两个链表连接起来,返回l1链表的头节点即可。
这里需要注意:再l2链表的结尾,要将尾节点的next指针置为NULL;
#include <cstddef> class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode* list1,*l1; l1=list1=(ListNode*)malloc(sizeof(ListNode)); ListNode* list2, *l2; l2=list2=(ListNode*)malloc(sizeof(ListNode)); ListNode* ptail=pHead; while(ptail) { if(ptail->val<x){ //尾插到l1里 l1->next=ptail; l1=l1->next; } else{ l2->next=ptail; l2=l2->next; } ptail=ptail->next; } l2->next=NULL; l1->next=list2->next; ListNode* ret=list1->next; free(list1); free(list2); list1=list2=NULL; return ret; } };