【LeetCode】203.移除链表元素
原题链接：🍏移除链表元素🍏
题目：给你一个链表的头节点
head和一个整数val，请你删除链表中所有满足Node.val == val的节点，并返回 新的头节点 。
要想删除当前元素，需要知道当前元素的位置，及前一个元素的位置，并且保存下一个元素的位置。
所以我们需要三个指针：
一个指针命名为cur，作用是遍历；
一个指针命名为prev，指向位置为cur的前一个位置，作用是删除（prev->next=cur->next）；
一个next指针用来保存cur的后一个位置，确保free掉cur后仍然可以找到下一元素。
代码实现：
/* 解题思路：从头节点开始进行元素删除，每删除一个元素，需要重新链接节点 */ struct ListNode* removeElements(struct ListNode* head, int val) { if(head == NULL) return NULL; struct ListNode* cur = head; struct ListNode* prev = NULL; while(cur) { //如果当前节点是需要删除的节点 if(cur->val == val) { //首先保存下一个节点 struct ListNode* next = cur->next; //如果删除的为头节点，更新头节点 //否则让当前节点的前趋节点链接next节点 if(prev == NULL) { head = cur->next; } else { prev->next = cur->next; } //释放当前节点，让cur指向next free(cur); cur = next; } else { //如果cur不是需要删除的节点，则更新prev,cur prev = cur; cur = cur->next; } } return head; }
注意：考虑极端情况，如首个位置就是val的情况，作单独处理。
【LeetCode】206.反转链表
原题链接：🍏反转链表🍏
题目：给你单链表的头节点
head，请你反转链表，并返回反转后的链表。
思路一
同样的我们需要三个指针来完成这一操作：
- 一个指针命名为cur，作用是遍历；
- 一个指针命名为prev，作用是拿到cur的前一个地址，而后改变cur->next指向prev；
- 一个指针命名为next，作用是保存cur的后一个位置，防止修改cur->next后找不到cur的后一个位置。
代码实现：
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev = NULL; struct ListNode* cur = head, * next = head; if (cur)// 检查cur是否为空 { next = cur->next; } while (cur) { // 往后走 prev = cur; cur = next; if(next)// 检查next是否为空 next = next->next; } return prev; }
思路二
取结点头插，完成逆置。
大家只要掌握了头插就很简单了。
代码实现：
// 取节点头插的思想完成逆置 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; //头插新节点，更新头 cur->next = newhead; newhead = cur; cur = next; } return newhead; }
【LeetCode】876.链表的中间结点
原题链接：🍏链表的中间结点🍏
题目：给你单链表的头结点
head，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
快慢指针法
若想找到中间结点，我们可以定义两个指针：
- 一个命名为slow，令slow每次走一步；
- 一个命名为fast，令fast每次走两步。
这样当fast为NULL，或fast->next为NULL时，slow恰好处于中间位置，最后返回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; }
【LeetCode】剑指Offer 22.链表中倒数第k个结点
原题链接：🍏链表中倒数第k个结点🍏
题目：输入一个链表，输出该链表中倒数第k个节点。
快慢指针法
同样需要快慢指针的方法。
令fast先走k步，slow不动，然后slow与fast同时向后走，直到fast为NULL，此时slow的位置就是倒数第k个位置。
代码实现：
struct ListNode* getKthFromEnd(struct ListNode* head, int k) { struct ListNode* slow=head,* fast=head; while(k--) { if(fast==NULL) { return NULL; } fast=fast->next; } while(fast) { slow=slow->next; fast=fast->next; } return slow; }
【LeetCode】21.合并两个有序链表
原题链接：🍏合并两个有序链表🍏
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：取小的尾插。
注意：极端情况的判断，如其中一个链表为空等等。
代码实现：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if(list1==NULL)// 判断其中一个链表为空的情况 { return list2; } if(list2==NULL)// 判断其中一个链表为空的情况 { return list1; } struct ListNode* head=NULL,*tail=NULL; while(list1 && list2) { if(list1->val<list2->val) { if(head==NULL)// 头结点直接赋值 { head=tail=list1; } else// 尾插 { tail->next=list1; tail=tail->next; } list1=list1->next; } else { if(head==NULL)// 头结点直接赋值 { head=tail=list2; } else// 尾插 { tail->next=list2; tail=tail->next; } list2=list2->next; } } if(list1)// list1有剩余 { tail->next=list1; } if(list2)// list2有剩余 { tail->next=list2; } return head; }
【LeetCode】剑指Offer Ⅱ 27.回文链表
原题链接：🍏回文链表🍏
题目：给定一个链表的 头节点
head，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
思路：找到中间结点，将后半部分逆置，最后令前后两部分一一对比，如果结点的值全部相同，则为回文。
刚好我们可以利用上面实现过的函数：链表的中间结点和反转链表。
代码实现：
// 找到中间结点 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; } // 反转一个单链表 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* tail = NULL; struct ListNode* cur = head, * next = head; while (next) { next = cur->next; cur->next = tail; tail = cur; cur = next; } return tail; } // 判断回文结构 bool isPalindrome(struct ListNode* head) { struct ListNode* mid=middleNode(head); struct ListNode* newhead=reverseList(mid); while(head && newhead) { if(head->val!=newhead->val) { return false; } else { head=head->next; newhead=newhead->next; } } return true; }
