【数据结构】链表OJ
Yan-英杰的主页
悟已往之不谏 知来者之可追
目录
编辑
编辑二、分享：OJ调试技巧
编辑四、链表中倒数第k个结点
一、移除链表元素
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]示例 2：
输入：head = [], val = 1
输出：[]示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]提示：
- 列表中的节点数目在范围
[0, 104]内1 <= Node.val <= 500 <= val <= 50
方法一：
代码解析:
struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* prev = NULL;struct ListNode* cur = head;while(cur){if(cur->val != val){prev = cur;cur = cur->next;}else{if(prev == NULL){head = cur->next;free(cur);cur = head;}else{prev->next = cur->next;free(cur);cur = prev->next;}}}return head;
}画图解析:
方法二：
代码解析：
struct ListNode* removeElements(struct ListNode* head, int val){if(head == NULL){return NULL;}struct ListNode* newHead = NULL,*tail = NULL;struct ListNode* cur = head;while(cur){if(cur->val != val){ //尾插if(tail == NULL){newHead = tail = cur;}else{tail->next =cur;tail = tail->next;}cur = cur->next;}else{struct ListNode* next = cur->next;free(cur);cur = next;}}if(tail)tail->next = NULL;return newHead;
}画图解析:
二、分享：OJ调试技巧
LeetCode在线调试功能需要付费，我们可以自己在编辑器进行调试，写个模板，每次用到复制过去直接调试即可
int main()
{struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));n1->val = 7;n2->val = 7;n3->val = 7;n4->val = 7;n5->val = 7;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;removeElements(n1,7);
}
三、链表的中间结点
示例 1：
输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。示例 2：
输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。提示：
- 链表的结点数范围是
[1, 100]1 <= Node.val <= 100
代码解析：
此题我们学会了快慢指针
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow,* fast;slow = fast = head;while(fast && fast->next)//节点为单数或者双数时出现的条件{slow = slow->next;fast = fast->next->next;}return slow;
}画图解析：
四、链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
实例：
输入：1,{1,2,3,4,5}
返回值：{5}代码解析：
此题依旧使用快慢指针
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {if(pListHead == NULL){return NULL;}struct ListNode* slow,* fast;slow = fast = pListHead;//fastwhile(k--){if(fast == NULL){return NULL;}fast = fast->next;}while(fast){slow = slow->next;fast = fast->next;}return slow;
}画图解析：
