Huge Lemon的博客

链表的中间结点

2020-02-29

LeetCode 876. Middle of the Linked List

题目描述

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

提示：

  • 给定链表的结点数介于 1 和 100 之间。

思路

思路一

先求出链表的长度 length，再进行计数遍历，遍历到 length / 2 为止，返回该结点。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 int LinkLength(struct ListNode* head){
     int len = 0;
     while(head != NULL){
         head = head->next;
         len++;
     }
     return len;
 }


struct ListNode* middleNode(struct ListNode* head){
    if(!head || !head->next)
        return head;
    int len = LinkLength(head);
    struct ListNode* p = head;
    for(int i = 0; i < len / 2; i++){
        p = p->next;
    }
    return p;
}

思路二

设置快慢指针 fast，slow。其中 fast 的步长为 $2$，slow 的步长为 $1$，那么在相同时间的前提下 fast 走过的链表长度就是 slow 走过长度的两倍。当 fast 抵达链表末尾时，slow 恰好指向链表的中间结点，此时 return slow。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head, *slow = head;
    while (fast != NULL && fast->next != NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
Tags: 算法 LeetCode
← 删除链表的倒数第N个节点 重排链表 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏