【leetcode.876】链表的中间结点

叁歲伎倆 2022-12-12 15:08 80阅读 0赞

## 一、题目描述 ##

给定一个带有头结点 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 之间。

--------------------

### 二、思路 ###

思路1：遍历整个链表，将结点依次存入数组中，最后返回数组中间的结点即可。时间复杂度和空间复杂度都为O(n)

思路2：不用开辟数组，只需要获取到链表中间结点的index即可，然后进行第二次遍历。时间复杂度为O(n)，空间复杂度为O(1)。

代码如下：

public ListNode middleNode(ListNode head) {
            int length = 0;
            ListNode temp = head;
            while (temp != null) {
                length++;
                temp = temp.next;
            }
    
            int middle = length % 2 == 0 ? length / 2 : (length - 1) / 2;
            int index = 0;
            while (index < middle) {
                index++;
                head = head.next;
            }
    
            return head;
        }

思路3：快慢指针法，慢指针步伐为1，快指针步伐为2。那么当快指针到达链表末尾时，慢指针位于链表中间。时间复杂度为O(n)，空间复杂度为O(1)。

代码如下：

public ListNode middleNode(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;
    
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }
    
            return slow;
        }

在判断链表是否成环时[【leetcode.141&142】环形链表及拓展][leetcode.141_142]，也可以使用快慢指针法。

[leetcode.141_142]: https://blog.csdn.net/qq_33591903/article/details/82966751?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160207926319195240448180%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=160207926319195240448180&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-3-82966751.pc_v1_rank_blog_v1&utm_term=%E9%93%BE%E8%A1%A8&spm=1018.2118.3001.4187