# 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
}
```