【数据结构】链表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 <= 50
• 0 <= 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;
}

        画图解析：