# 2022-05-19

## [876. Middle of the Linked List](https://leetcode.com/problems/middle-of-the-linked-list/)

### Description

Given the `head` of a singly linked list, return *the middle node of the linked list*.

If there are two middle nodes, return **the second middle** node.

**Example 1:**

![](https://img.content.cc/a/2022/05/19/08-59-37-482-7b33914b686ad5b8b41b13bcaeb18af6-944d01.jpeg)

```
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
```

**Example 2:**

![](https://img.content.cc/a/2022/05/19/09-00-08-265-4c1a7e6c2b93740ccdbb6bd9873922a5-ae0913.jpeg)

```
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
```

**Constraints:**

* The number of nodes in the list is in the range `[1, 100]`.
* `1 <= Node.val <= 100`

### Solution

#### Approach #0: Single Pointer

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    first, second := head, head
    count := 0
    for first.Next != nil {
        count++
        first = first.Next
    }

    for i := 0; i < count/2+count%2; i++ {
        second = second.Next
    }
    return second
}
```

#### Approach #1: **Fast and Slow Pointer**

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    first, second := head, head
    for second != nil && second.Next != nil {
        first = first.Next
        second = second.Next.Next
    }
    return first
}
```

#### Approach #2: Output to Array

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    var l []*ListNode
    for head != nil {
        l = append(l, head)
        head = head.Next
    }
    return l[len(l)/2]
}
```

## [19. Remove Nth Node From End of List](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)

### Description

Given the `head` of a linked list, remove the `nth` node from the end of the list and return its head.

**Example 1:**

![](https://img.content.cc/a/2022/05/19/09-18-34-896-da94924691c022d09f800646b9b72e35-995240.jpeg)

```
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
```

**Example 2:**

```
Input: head = [1], n = 1
Output: []
```

**Example 3:**

```
Input: head = [1,2], n = 1
Output: [1]
```

**Constraints:**

* The number of nodes in the list is `sz`.
* `1 <= sz <= 30`
* `0 <= Node.val <= 100`
* `1 <= n <= sz`

**Follow up:** Could you do this in one pass?

### Solution

#### Approach #0

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    first := head
    count := 0
    for first != nil {
        count++
        first = first.Next
    }
    newHead := &ListNode{0, head}
    second := newHead
    for i := 0; i < count-n; i++ {
        second = second.Next
    }
    second.Next = second.Next.Next
    return newHead.Next
}
```

#### Approach #1

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var nodeList []*ListNode
    newHead := &ListNode{0, head}
    for cur := newHead; cur != nil; cur = cur.Next {
        nodeList = append(nodeList, cur)
    }
    prev := nodeList[len(nodeList)-n-1]
    prev.Next = prev.Next.Next
    return newHead.Next
}
```

#### Approach #2

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    newHead := &ListNode{0, head}
    fast, slow := newHead, newHead
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return newHead.Next
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://a.b.cr/dictionary/algorithm/diary/2022/05/2022-05-19.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.