2022-05-19

876. 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:

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

Example 2:

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

/**
 * 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

/**
 * 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

/**
 * 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

Description

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

Example 1:

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

/**
 * 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

/**
 * 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

/**
 * 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
}