Leetcode:876. 链表的中间结点 【详解】

结点 【详解】"/>

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指针指的结点就是中间结点。

奇数个结点

 偶数个结点的情况