Leecode刷题 876. 链表的中间结点——链表

题目：

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fizz-buzz
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

知识点

c语言链表详解（超详细）

思路：

来自官方的三种思路：

方法一：数组

链表的缺点在于不能通过下标访问对应的元素。因此我们可以考虑对链表进行遍历，同时将遍历到的元素依次放入数组 A 中。如果我们遍历到了 N 个元素，那么链表以及数组的长度也为 N，对应的中间节点即为 A[N/2]。

复杂度分析

• 时间复杂度：O(N)，其中 N 是给定链表中的结点数目。
• 空间复杂度：O(N)，即数组 A 用去的空间。

struct ListNode* middleNode(struct ListNode* head)
{
    //暴力数组法
    struct ListNode *nodeIt = head;    //迭代器
    struct ListNode *nodeTable[101];  //给定链表的结点数介于 1 和 100 之间。
    int  nodeTableCnt = 0;
    int  nodeMiddle   = 0;
    //存储到数组中
    while (nodeIt != NULL) 
    {
        nodeTable[nodeTableCnt] = nodeIt;
        nodeIt = nodeIt->next;
        nodeTableCnt++;
    }
    //计算中间
    nodeMiddle = nodeTableCnt/2;
    return nodeTable[nodeMiddle];
}

作者：goodgoodday
链接：https://leetcode.cn/problems/middle-of-the-linked-list/solution/lian-biao-de-zhong-jian-jie-dian-cyu-yan-elyz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：单指针法

我们可以对方法一进行空间优化，省去数组 A。

我们可以对链表进行两次遍历。第一次遍历时，我们统计链表中的元素个数 N；第二次遍历时，我们遍历到第 N/2 个元素（链表的首节点为第 0 个元素）时，将该元素返回即可。

复杂度分析

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

这就是自己采用的思路：
第一种不严谨，后面是改进的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode * temp = head;
    int n = 1;
    while(temp->next != NULL)
    {
        temp = temp->next;
        n++;
    } 
    temp = head;
    for(int i = 1;i < (n/2+0.5);i++)
    {
        temp = temp->next;
    }
    return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（上面）初始化为n= 1，后面用for(int i = 1;i < (n/2+0.5);i++)
显然上面这种不严谨，因为没有考虑到head = NULL的情况。，另外，其实，这种方法最大问题是在，while(temp->next != NULL)，没有判断本位是不是空。

（下面）初始化为n=0，后面用for(int i = 0;i < n/2;i++)
其实这里，经过验证，只要for(int i = 0;i < n/2;i++)或者for(int i = 1;i < (n/2+0.5);i++)二者选其一，就可以，不用管n=0还是1，因为关键在于，while(temp != NULL)，是判断本次的。知道长度之后，一定是可以得到正确的结果。而，对于n=0还是1，也是考虑到，用0作为初始值还是用1作为初始值，有不同的考虑。

修改循环条件之后：

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode * temp = head;
    int n = 0;
    while(temp != NULL)//这里改成判断当前的这个就可以使用n/2了
    {
        temp = temp->next;
        n++;
    } 
    temp = head;
    for(int i = 0;i < n/2;i++)
    {
        temp = temp->next;
    }
    return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法三：快慢指针法

我们可以继续优化方法二，用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。
复杂度分析

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

既然要快指针走两步，说明链表的长度至少为3，所以当长度小于3的时候需要我们自己判断,base case:
长度为1直接返回 return head;
长度为2 返回第二个节点 return head.next;
》
下面我们要做的就是让指针动起来，然后找到停止条件
快指针一定在前面，所以条件判断的时候，我们只需要判断快指针的位置即可，打个比方就很清楚了：
假设长度为奇数的链表为[1,2,3,4,5],当快指针走到5的位置的时候停止，此时慢指针正好在中点3的位置。也就是说 fast.next != null
假设长度为偶数的链表为[1,2,3,4,5,6],当快指针走到5的位置的时候不能停止，因为此时后面还有一个6，还要继续往前走，当快指针停在了6的后面的位置的时候，也就是为空，此时慢指针正好在中点3的位置。也就是说 fast != null

错误程序：

struct ListNode* middleNode(struct ListNode* head){
    if(head == NULL)
        return head;
    struct ListNode * slow = head;
    struct ListNode * fast = head; 
    while(fast->next != NULL && fast != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    } 
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12

我已经加了head是空指针的判断了，还是报错：
runtime error: member access within null pointer of type 'struct ListNode' [solution.c]，百思不得其解，最后看到这篇文章明白了：LeetCode报错:runtime error: member access within null pointer of type ‘struct ListNode’
while循环里面的判断，是先判断fast->next,后判断fast，但有可能fast是nullptr，如果是这样的话，先判断fast->next就会出错，这句话就跑不过，最后才发现是while中判断的顺序不能变。将程序改成下即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode * slow = head;
    struct ListNode * fast = head; 
    if(head == NULL)
        return head;
    while(fast != NULL && fast->next != NULL)
    {
        slow = slow->next;
        fast = fast->next->next;
    } 
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21