移除链表元素
链接: 移除链表元素
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { //设置俩个指针 //prev用来记录val前面的指针 //假设将prev的指向head的前面，即为NULL struct ListNode* prev = NULL; //cur用来判断,cur指向链表第一个 struct ListNode* cur = head; //利用prev和cur进行循环 //当cur为NULL停止 while(cur != NULL) { if(cur->val != val) { //cur的值不等于val时 //prev向后移动一步 //cur向后移动一步 prev = cur; cur = cur->next; } else { //判断如果一个值为val时，此时prev任然为NULL; //需要将这种cur向后移 if(prev == NULL) { //将head指向下一个 head = cur->next; //释放cur free(cur); //cur重新指向head的值 cur = head; } else { //cur的值等于val时 //将prev指向的地址向后移动一步 prev->next = cur->next; //释放cur所在的内存 free(cur); //将粗人指向新的prev后面的位置 cur = prev->next; } } } return head; }
链表的中间结点
链接: 链表的中间结点
思路：使用快慢指针进行解答
1.定义一个快指针和慢指针均指向头指针
2.快指针一次走俩步，慢指针一次走一步
3.当快指针为空指针或者快指针的下一个指针为空时结束
代码详解：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { //定义一个快指针，一次走俩格 struct ListNode* fast = head; //定义一个慢指针，一次走一格 struct ListNode* slow = head; while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; }
返回倒数第k个结点
链接: 返回倒数第k个结点
思路：使用先后指针解答
1.定义一个先走指针fast和慢走指针slow
2.先走指针要比慢走指针快k步
3.然后俩个指针同时进行移动
4.当先走指针遇到NULL时停止
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int kthToLast(struct ListNode* head, int k) { //定义一个先走指针， struct ListNode* fast = head; //定义一个慢走指针 struct ListNode* slow = head; //先走指针比慢走指针快k步 while(k--) { fast = fast->next; } //俩个指针一起走 while(fast != NULL) { fast = fast->next; slow = slow->next; } return slow->val; }
合并俩个有序链表
链接:合并俩个有序链表
思路：
1.定义cur1指向list1的头结点，定义cur2指向list2的头结点，定义head和end指向空
2.cur1用来遍历list1，cur2用来遍历list2，head用来记录合并后的头结点，end用来记录合并后的尾结点，以确保可以向后添加结点
3.判断是否有空，但凡有一个为空，就可以返回另外一个；如果俩个都不为空，需要设置合并后的头结点head
4.当俩个都不为空，进入循环，向end后面接结点
5.当俩个中间有一个为空时，可以只在将另一个接在end后面
代码:
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //设置四个结点 struct ListNode* cur1 = list1; struct ListNode* cur2 = list2; struct ListNode* head = NULL; struct ListNode* end = NULL; //判断如何都不为空 if (cur1 && cur2) { //将合并后头结点head指向小值 if (cur1->val < cur2->val) { head = end = cur1; cur1 = cur1->next; } else { head = end = cur2; cur2 = cur2->next; } } //cur1与cur2都不为空所以不需要判断else，如果没有else，设置完头结点head后，有一个可能为空，导致返回。 else if (cur1 == NULL)//cur1为空，返回cur2 { return cur2; } else if (cur2 == NULL)//cur2为空。返回cur1 { return cur1; } //俩个都不为空进行插入链表 while (cur1 && cur2) { //每次插入都需要，将cur和end向后移动 if (cur1->val <= cur2->val) { end->next = cur1; cur1 = cur1->next; end = end->next; } else { end->next = cur2; cur2 = cur2->next; end = end->next; } } //如果其中一个为空，可以直接将另一个后面的全部接在end后面 if (cur1 == NULL) { end->next = cur2; } if (cur2 == NULL) { end->next = cur1; } return head; }
链表分割
链接:链表分割
思路：
1.首先需要创建俩个哨兵结点来将大值结点与小结点分割开
2.使用四个指针指向俩个哨兵结点，begin1、begin2、end1、end2
3.begin1与begin2保留俩个哨兵结点的位置，end1与end2接后面的结点
4.然后将俩个哨兵结点相连，注意需要释放空间
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Partition { public: ListNode* partition(ListNode* pHead, int x) { //创建俩个哨兵结点 //使用begin1与end1指向第一个哨兵 //使用begin2与end2指向第二个哨兵 struct ListNode* begin1; struct ListNode* begin2; struct ListNode* end1; struct ListNode* end2; begin1 = (struct ListNode*)malloc(sizeof(struct ListNode)); begin2 = (struct ListNode*)malloc(sizeof(struct ListNode)); if(begin1 == NULL || begin2 == NULL) { perror("malloc fail"); return NULL; } begin1->next = NULL; begin2->next = NULL; end1 = begin1; end2 = begin2; //将小于x的结点接在begin1后面 //将大于等于x的结点接在begin2后面 while(pHead != NULL) { if(pHead->val < x) { end1->next = pHead; end1 = end1->next; } else { end2->next = pHead; end2 = end2->next; } pHead = pHead->next; } //将end1与end2后面置空 end1->next = NULL; end2->next = NULL; //将大于等于x的结点接在小于x的结点后面 end1->next = begin2->next; //将小于x的第一个结点设置为头结点 pHead = begin1->next; //注意需要释放malloc创建的堆区已经野指针问题 free(begin1); free(begin2); begin1 = begin2 = end1 = end2 = NULL; return pHead; } };
相交链表
链接: 相交链表
思路：
1.定义俩个指向链表的指针和俩个计算结点个数（长度）的变量
2.求出俩个链表有几个结点，即链表的长度
3.如果最后一个结点处，二者并没有相交，则返回NULL
4.将俩个链表的结点个数（长度）相减，让结点个数（长度）多（长）的先走相减的个数。
5.最后俩条链表同时走，遇到相同结点时结束
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //设置L1和L2计算俩条链的长度 int L1 = 1, L2 = 1; //设置俩个指针指向俩条链的头结点 struct ListNode* cur1 = headA; struct ListNode* cur2 = headB; //计算L1的长度 while(cur1->next != NULL) { cur1 = cur1->next; ++L1; } //计算L2的长度 while(cur2->next != NULL) { cur2 = cur2->next; ++L2; } //判断如果俩个直接的最好交点不在一起则直接返回NULL if(cur1 != cur2) { return NULL; } //计算链的长度差 int L = L1 - L2; //将移动的指针重新指向头结点 cur1 = headA; cur2 = headB; //让长度较长的指针先走L步 if(L > 0) { while(L--) { cur1 = cur1->next; } } else { while(L++) { cur2 = cur2->next; } } //俩个指针同时走，发现相同时停止 while(cur1 != cur2) { cur1 = cur1->next; cur2 = cur2->next; } return cur1; }
环形链表
链接: 环形链表
思路：
1.判断是否存在空结点和只有一个结点的情况
2.定义一个快结点和一个慢结点
3.快结点一次走俩步，慢结点一次走一步
4.当二者相遇时结束
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { //判断是否存在空链表或者链表中只存在一个结点 if(head == NULL || head->next == NULL) { return false; } //定义一个快结点和慢结点 struct ListNode* fast = head; struct ListNode* slow = head; //快结点一次走俩步 //慢结点一次走一步 while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; //相遇时结束 if(fast == slow) { return true; } } return false; }
链表的回文结构
链接: 链表的回文结构
思路：
1.判断当存在空链表或者当个链表时返回true
2.设置快慢指针求得中间结点
3.使用三个指针翻转后半段链表
4.使用一前一后俩个指针判断是否为回文结构
难点：使用三个指针翻转链表时，循环停止的条件为中间的指针为空，此时需要第三个结点在循环内初始化，这样才能保证后面每一个链表都能翻转过来，并且当第三个结点为空时，不会执行next
- 代码实现：
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class PalindromeList { public: bool chkPalindrome(ListNode* A) { //链表为空或者链表只有一个返回true if(A == NULL || A->next == NULL) { return true; } //设置快慢指针 //快指针一次走俩步 //慢指针一次走一步 struct ListNode* fast = A; struct ListNode* slow = A; //寻找中间结点 while(fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } //slow此时所在位置为中间结点 //从中间结点往后开始翻转链表 struct ListNode* cur = slow->next; while(cur != NULL) { struct ListNode* cur_next = cur->next; cur->next = slow; slow = cur; cur = cur_next; } //设置一个头结点和尾结点 struct ListNode* tail = slow; struct ListNode* head = A; //一前一后开始比较 //比较正确，比较下一个 //比较错误，返回错误 while( head != tail)//奇数时二者相遇 { if(head->val != tail->val) { return false; } if(head->next == tail) { //偶数时head的下一个是tail return true; } head = head->next; tail = tail->next; } return true; } };
