当前位置：首页 > news >正文

链表oj题1(Leetcode)——移除链表元素，反转链表，链表的中间节点，

news 2025/12/15 21:45:43

链表OJ

一，移除链表元素
- 1.1分析
- 1.2代码
二，找到链表的中间节点
- 2.1分析
- 2.2代码
三，反转链表
- 3.1分析
- 3.2代码
四，找到链表中倒数第k个节点
- 4.1分析
- 4.2代码

一，移除链表元素

移除链表元素
在这里插入图片描述

1.1分析

这里的删除要分成两种情况来考虑，因为这个题目给了我们头节点，所以分成头删和非头删。因为要记录下一个节点的位置，所以1我们这里选择新增两个指针方便记录。因为我们已经熟悉了链表所以这代码对我们来说还是很容易的。

1.2代码

struct ListNode* removeElements(struct ListNode* head, int val){struct ListNode* cur=head;struct ListNode* prev=NULL;//遍历链表找满足条件的valwhile(cur){if(cur->val==val){//头删特殊处理if(cur==head){head=cur->next;free(cur);cur=head;}//一般化删除else{prev->next=cur->next;free(cur);cur=prev->next;}}else{prev=cur;cur=cur->next;}}return head;
}

二，找到链表的中间节点

链表的中间节点
在这里插入图片描述

2.1分析

这里要让我们找到中间的节点，我们从题目出发，有个非常巧妙的写法就是快慢指针，我们定义两个指针，慢指针正常一次走一步，而快指针一次走两步，那么当快指针走到结束的时候慢指针就在中间位置了。

2.2代码

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;
}

三，反转链表

反转链表
在这里插入图片描述

3.1分析

创建一个newhead链表，把原链表从左到右一个一个取出来放到newhead中去。

3.2代码

struct ListNode* reverseList(struct ListNode* head){struct ListNode*cur=head;struct ListNode*newhead=NULL;while(cur){struct ListNode*next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

四，找到链表中倒数第k个节点

牛客——找到链表中倒数第k个节点
在这里插入图片描述

4.1分析

这里我们依旧选择快慢指针。
在这里插入图片描述
我们假设k是3，那么我们定义fast，和slow两个指针，第一让fast先走k下，然后两个指针一起走，那么当fast走到NULL，slow所在的位置就是倒数第k个位置。

4.2代码

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {// write code herestruct ListNode*fast=pListHead;struct ListNode*slow=pListHead;while(k--){if(fast==NULL){return NULL;}else {fast=fast->next;}}while(fast){fast=fast->next;slow=slow->next;}return slow;
}