结点 【详解】"/>
Leetcode:876. 链表的中间结点 【详解】
目录
题目
题目解析:
代码展示
图解
题目
给你单链表的头结点
head
,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
难度:简单
题目链接:876. 链表的中间结点
提示:
- 链表的结点数范围是
[1, 100]
1 <= Node.val <= 100
题目解析:
题目给出的链表结点的存储
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
由题目可以知道,题目要求返回中间的结点。
- 方法1:两次遍历指针,第一遍遍历计算结点个数(奇数个还是偶数个),第二遍去查找中间结点并返回。
- 方法2:使用快慢指针来控制(只需遍历一遍链表即可) ,当快指针走两步,慢指针走一步。当快指针走到最后一个结点,或者走到NULL。即遍历完一遍指针。返回慢指针指向的结点。
代码展示
方法1 :
struct ListNode* middleNode(struct ListNode* head){struct ListNode * pl = head;int i = 0;//遍历第一遍while(pl != NULL){pl = pl->next;i++;}//第二次遍历int t = i/2;while(t--){head = head->next;}return head;}
图解
方法二:
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* middleNode(struct ListNode* head){//先让快慢指针指向头结点struct ListNode *low = head, *fast = head;while(fast && fast->next){low = low->next; //下一个节点fast = fast->next->next; //下一个节点的节点}return low; //返回慢指针,指向的节点}
这里的 fast&&fast->next 表示 fast不是空指针或者fast的下一个节点不是空,就执行while循环中的语句。
图解:
第一步,起初都指向第一个结点
第二步,进行遍历。慢指针走一步,快指针走两步。
第三步,遍历完成。当快指针指到最后一个结点 或者 指向NULL时;此时的low指针指的结点就是中间结点。
奇数个结点
偶数个结点的情况
更多推荐
Leetcode:876. 链表的中间结点 【详解】
发布评论