链表面试OJ题（1）

今天讲解两道链表OJ题目。

1.链表的中间节点 

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 

 

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 

---

方法1【 双指针】

时间复杂度：O(N)

思想：两个指针，faster的速度是slow两倍，则当faster走到结尾时，slow则走到链表中间。

易错：循环条件 

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode*faster=head;struct ListNode*slow=head;while(faster && faster->next)//条件没想到{faster=faster->next->next;slow=slow->next;}return slow;
}

---

2.移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。 

示例 

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

---

方法1【三指针--无哨兵位】

时间复杂度：O(N)

思想：三个指正，cur负责对比val，tmp负责存储删除元素的下一个元素地址，prve负责存储删除元素的上一个元素地址

易错：

• 记住prve是cur的前一个元素，那么它从NULL开始
• 循环条件
• 记得处理头节点和尾节点
• 造成野指针的错误❌

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) 
{struct ListNode*cur=head;struct ListNode*prve=NULL;while(cur){if(cur->val == val){struct ListNode*tmp=cur->next;free(cur);if(prve){prve->next=tmp;}                                   else{head=tmp;}                          cur=tmp;}else{prve=cur;cur=cur->next;}}return head;}

---

方法2【双指针---无哨兵位】

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) 
{struct ListNode*newhead=NULL;struct ListNode*tail=NULL;struct ListNode*cur=head;while(cur){if(cur->val != val){if(newhead == NULL){newhead=tail=cur;}else{tail->next=cur;tail=tail->next;}cur=cur->next;}else{struct ListNode*tmp=cur->next;free(cur);cur=tmp;}if(tail){tail->next=NULL;}} return newhead;          
}//❌改进

---

那有哨兵位怎么写呢？

当然，这道题还可以联系前面顺序表（移除val）。

代码---------→【唐棣棣 (TSQXG) - Gitee.com】

联系---------→【邮箱：[e-mail]】