1.输入链表头节点,奇数长度返回中点,偶数长度返回上中点 。
1.1.快慢指针。
1.2.单指针。
1.3.数组。
2.输入链表头节点,奇数长度返回中点,偶数长度返回下中点 。这道题是leetcode上的第876道题,叫【链表的中间节点】。
2.1.快慢指针。
2.2.单指针。
2.3.数组。
golang代码如下:
package main
import "fmt"
func main() {
if true {
fmt.Println(2)
head := &ListNode{}
node := head
node.Val = 0
node.Next = &ListNode{}
node = node.Next
node.Val = 1
fmt.Println(middleNode1_1(head), "偶上中,快慢指针")
fmt.Println(middleNode1_2(head), "偶上中,单指针")
fmt.Println(middleNode1_3(head), "偶上中,数组")
fmt.Println(middleNode2_1(head), "偶下中,快慢指针")
fmt.Println(middleNode2_2(head), "偶下中,单指针")
fmt.Println(middleNode2_3(head), "偶下中,数组")
}
if true {
fmt.Println("---------------")
fmt.Println(3)
head := &ListNode{}
node := head
node.Val = 0
node.Next = &ListNode{}
node = node.Next
node.Val = 1
node.Next = &ListNode{}
node = node.Next
node.Val = 2
fmt.Println(middleNode1_1(head), "偶上中,快慢指针")
fmt.Println(middleNode1_2(head), "偶上中,单指针")
fmt.Println(middleNode1_3(head), "偶上中,数组")
fmt.Println(middleNode2_1(head), "偶下中,快慢指针")
fmt.Println(middleNode2_2(head), "偶下中,单指针")
fmt.Println(middleNode2_3(head), "偶下中,数组")
}
if true {
fmt.Println("---------------")
fmt.Println(1)
head := &ListNode{}
node := head
node.Val = 0
fmt.Println(middleNode1_1(head), "偶上中,快慢指针")
fmt.Println(middleNode1_2(head), "偶上中,单指针")
fmt.Println(middleNode1_3(head), "偶上中,数组")
fmt.Println(middleNode2_1(head), "偶下中,快慢指针")
fmt.Println(middleNode2_2(head), "偶下中,单指针")
fmt.Println(middleNode2_3(head), "偶下中,数组")
}
}
type ListNode struct {
Val int
Next *ListNode
}
//1.输入链表头节点,奇数长度返回中点,偶数长度返回上中点 。
//快慢指针
func middleNode1_1(head *ListNode) *ListNode {
pre := &ListNode{} //虚拟头节点
pre.Next = head
pre.Val = 1
slow := pre
fast := pre
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
//1.输入链表头节点,奇数长度返回中点,偶数长度返回上中点 。
//单指针
func middleNode1_2(head *ListNode) *ListNode {
n := 0
cur := head
for cur != nil {
n++
cur = cur.Next
}
k := 0
cur = head
n = (n - 1) / 2
for k < n {
k++
cur = cur.Next
}
return cur
}
//1.输入链表头节点,奇数长度返回中点,偶数长度返回上中点 。
//数组
func middleNode1_3(head *ListNode) *ListNode {
list := make([]*ListNode, 0)
for head != nil {
list = append(list, head)
head = head.Next
}
return list[(len(list)-1)/2]
}
//2.输入链表头节点,奇数长度返回中点,偶数长度返回下中点 。这道题是leetcode上的第876道题,叫【链表的中间节点】。
//快慢指针
func middleNode2_1(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
//2.输入链表头节点,奇数长度返回中点,偶数长度返回下中点 。这道题是leetcode上的第876道题,叫【链表的中间节点】。
//单指针
func middleNode2_2(head *ListNode) *ListNode {
n := 0
cur := head
for cur != nil {
n++
cur = cur.Next
}
k := 0
cur = head
n /= 2
for k < n {
k++
cur = cur.Next
}
return cur
}
//2.输入链表头节点,奇数长度返回中点,偶数长度返回下中点 。这道题是leetcode上的第876道题,叫【链表的中间节点】。
//数组
func middleNode2_3(head *ListNode) *ListNode {
list := make([]*ListNode, 0)
for head != nil {
list = append(list, head)
head = head.Next
}
return list[len(list)/2]
}
执行结果如下: