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]
}
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
}
