11、链表中间节点

题目描述

链表的中间结点

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

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：3

说明：因为只有一个中间节点。

示例 2：

输入：[1,2,3,4,5,6]
输出：4

说明：有两个中间节点所以返回后面那个。

题目解析

又精心筛选了一个题目，本来想写一下删除节点的题目，然后发现这个题目更符合目前的节奏，所以先写一下这个题目，明天再给大家写删除节点的题目。

大家先不要看我的题解，先自己想一下怎么做。这个这个题目是想让我们找出中间节点，昨天的题目是让我们倒数第 K 个节点，想一下这两个题目有什么联系呢？

先说一下刚开始刷题的小伙伴可能会想到的题解，两次遍历链表，第一次遍历获取链表长度，第二次遍历获取中间链表。

这个方法很 OK，利用数组先将所有链表元素存入数组里，然后再直接获得中间节点。这个也很 OK，那么我们有没有一次遍历，且不开辟辅助空间的方法呢？

昨天的题目是一前一后双指针，两个指针之间始终相差 k-1 位，我们今天也利用一下双指针的做法吧。

这种类型的双指针是我们做链表的题目经常用到的，叫做快慢指针。

一个指针走的快，一个指针走的慢，这个题目我们可以让快指针一次走两步，慢指针一次走一步，当快指针到达链表尾部的时候，慢指针不就到达中间节点了吗？

链表中节点的个数有可能为奇数也有可能为偶数，这是两种情况，但是我们输出是相同的，那就是输出 slow 指针指向的节点，也就是两个中间节点的第二个。

代码

Java Code:

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;//快指针
        ListNode slow = head;//慢指针
        //循环条件，思考一下跳出循环的情况
        while (fast!=null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //返回slow指针指向的节点
        return slow;
    }
}

C++ Code:

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode * fast = head;//快指针
        ListNode * slow = head;//慢指针
        //循环条件，思考一下跳出循环的情况
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        //返回slow指针指向的节点
        return slow;
    }
};

JS Code:

var middleNode = function (head) {
  let fast = head; //快指针
  let slow = head; //慢指针
  //循环条件，思考一下跳出循环的情况
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
  }
  //返回slow指针指向的节点
  return slow;
};

Python Code:

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = head  # 快指针
        slow = head  # 慢指针
        # 循环条件，思考一下跳出循环的情况
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
        # 返回slow指针指向的节点
        return slow

Swift Code：

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var fast = head //快指针
        var slow = head //慢指针
        //循环条件，思考一下跳出循环的情况
        while fast != nil && fast?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
        }
        //返回slow指针指向的节点
        return slow
    }
}

Go Code:

func middleNode(head *ListNode) *ListNode {
	// 快慢指针
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}