题目

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

  • 链表的结点数范围是 [1, 100]
  • 1 <= Node.val <= 100

解题思路

首先想到的就是计算链表的长度，然后遍历链表到中间节点返回。这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
	n := 0
	for node := head; node != nil; node = node.Next {
		n++
	}

	for i := 0; i < n/2; i++ {
		head = head.Next
	}

	return head
}

书接上文142. 环形链表 II，其实仍然可以利用快慢针，因为快针每次走两步，慢针每次走一步，所以当快针走到链表末尾时，慢针正好在中间节点。这样只需要遍历一次链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for {
        if fast == nil || fast.Next == nil {
            break
        }
        slow = slow.Next
        fast = fast.Next.Next
    }

	return slow
}

这题比较简单，主要是后面有一题会同时用到链表的中间节点、链表逆序和链表的相交，所以这里先简单记录一下。