本文主要是介绍链表的中间结点算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

• 1、问题描述
• 2、单指针法
• 3、快慢指针法
• 总结

1、问题描述

给定一个头结点为 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，我们返回第二个结点。

2、单指针法

根据题目要求，要返回链表中间节点，需要知道链表有多少个节点，由于链表不能像数组一样，根据下标来取值，也不知道链表节点个数。所有，需要遍历整个链表，才能知道链表的长度，然后再根据链表长度 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. 代码如下：

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

2. 复杂度分析
   时间复杂度： O ( N ) O(N) O(N)，其中 N N N 是给定链表的结点数目。
   空间复杂度： O ( 1 ) O(1) O(1)，只需要常数空间存放变量和指针。

3、快慢指针法

当指针法需要遍历两次链表，如果只遍历一次链表，就能得到中间节点，这样的算法更加有效率。如果想要满足这样条件，那么必须要有两个指针，当一个快指针fast指向链尾时，第二个slow指针刚好指向中间节点。这两个指针都是从0开始，当慢指针slow一次只走一步，而快指针fast一次走两步，那么，当快指针走到链尾时，慢指针刚好为中间节点。
关键点在于如何判断循环结束语句。

1. 代码如下：

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

2. 复杂度分析
   时间复杂度： O ( N ) O(N) O(N)，其中 N N N 是给定链表的结点数目。
   空间复杂度： O ( 1 ) O(1) O(1)，只需要常数空间存放 slow 和 fast 两个指针。

总结

发现一个小技巧，在循环的时候，尽量减少计算，如果可以，尽量在循环题外处理计算。如遇到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)…这样计算量会大大较少。

这篇关于链表的中间结点算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！