给定一个头结点为 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:[1,2,3,4,5]
输出:此列表中的结点 3 (序列化形式:[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意,我们返回了一个 ListNode 类型的对象 ans,这样:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2:
输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
根据题目要求,要返回链表中间节点,需要知道链表有多少个节点,由于链表不能像数组一样,根据下标来取值,也不知道链表节点个数。所有,需要遍历整个链表,才能知道链表的长度,然后再根据链表长度
c
o
u
n
t
count
count,来求取链表中间节点
c
o
u
n
t
/
2
count/2
count/2。
也就是说,需要遍历两次链表就能得到中间节点。而中间节点判定如下:当长度为
c
o
u
n
t
count
count,
i
i
i从0开始,当
i
=
c
o
u
n
t
/
2
i=count/2
i=count/2时,即为中间节点。
/** 1. Definition for singly-linked list. 2. struct ListNode { 3. int val; 4. ListNode *next; 5. ListNode() : val(0), next(nullptr) {} 6. ListNode(int x) : val(x), next(nullptr) {} 7. ListNode(int x, ListNode *next) : val(x), next(next) {} 8. }; */ class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* list1 = head;//声明一个链结点指向头节点 int count = 0;//计数 while (list1 !=nullptr) { count++; list1 = list1->next;//遍历链表 } list1 = head;//第一次遍历完后,list1=nullptr,第二次遍历需要冲头 开始 int i=0; count = count / 2; while (i < count) { i++; list1 = list1->next;//遍历到中间节点结束。 } return list1; } };
当指针法需要遍历两次链表,如果只遍历一次链表,就能得到中间节点,这样的算法更加有效率。如果想要满足这样条件,那么必须要有两个指针,当一个快指针fast指向链尾时,第二个slow指针刚好指向中间节点。这两个指针都是从0开始,当慢指针slow一次只走一步,而快指针fast一次走两步,那么,当快指针走到链尾时,慢指针刚好为中间节点。
关键点在于如何判断循环结束语句。
class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* fast = head; ListNode* slow = head;//快、慢指针初始都指向链头 while (fast != NULL && fast->next != NULL) { slow = slow->next;//一次走一个节点 fast = fast->next->next;//一次走两个节点 } return slow; } };
发现一个小技巧,在循环的时候,尽量减少计算,如果可以,尽量在循环题外处理计算。如遇到while(i<count/2)这类情况,尽量将计算放在循环体外,比如,先 c o u n t = c o u n t / 2 ; 再 w h i l e ( i < c o u n t ) count=count/2;再while(i<count) count=count/2;再while(i<count)…这样计算量会大大较少。