目录
leetcode链表
1.删除链表中的节点
题目：删除链表中的节点，删除单链表的节点
答案：
type ListNode struct {
Val int
Next *ListNode
}
//删除
func deleteNode(node *ListNode) {
node.Val = node.Next.Val
node.Next = node.Next.Next
}
//读取
func readNode(node *ListNode) {
for {
if node != nil {
fmt.Println(node.Val)
node = node.Next
} else {
break
}
}
}
func main() {
one := ListNode{Val: 1}
two := ListNode{Val: 2}
three := ListNode{Val: 3}
four := ListNode{Val: 4}
five := ListNode{Val: 5}
one.Next = &two
two.Next = &three
three.Next = &four
four.Next = &five
deleteNode(&one)
readNode(&one)
}
2.删除链表中倒数第n个节点
题目：删除链表中倒数第n个节点
答案：
/*
解题思路：
1.先进行正删
2.再计算链表的长度，进行正删。删除的位置=链表长度-倒删位置
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
lenth := 1
lenNode := head
for {
if lenNode.Next != nil {
lenth++
lenNode = lenNode.Next
} else {
break
}
}
delhead := head
delhead2 := head
delIndex := lenth - n //删除位置
for index := 0; index < lenth; index++ {
if delIndex == 0 {
delhead2 = delhead.Next
break
}
if index == delIndex-1 {
delhead.Next = delhead.Next.Next
break
}
if delhead.Next != nil {
delhead = delhead.Next
}
}
return delhead2
}
3.反转链表
题目：反转链表
答案：
/*
解析：需要看视频理解：https://www.bilibili.com/video/BV1Lg411K7py/?spm_id_from=333.337.search-card.all.click&vd_source=6728716b092fdb6cc9a0ef2071c804ed
1.记录前一个节点，当前节点
2.记录下一个节点。
3.当前节点的下一个节点=前一个节点
移动前一个节点指向：
4.前一个节点=当前节点---移动前一个节点指向
6.当前节点=下一个节点---移动当前节点指向
6.循环开始下一个节点=当前节点的下一个节点（进入第2步）
*/
func reverseList(head *ListNode) *ListNode {
var prev *ListNode //前一个节点
var next *ListNode //前一个节点
curr := head //当前节点
for curr != nil {
next = curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
type ListNode struct {
Val int
Next *ListNode
}
func readNode(node *ListNode) {
for {
if node != nil {
fmt.Println(node.Val)
node = node.Next
} else {
break
}
}
}
func main() {
one := ListNode{Val: 1}
two := ListNode{Val: 2}
three := ListNode{Val: 3}
four := ListNode{Val: 4}
five := ListNode{Val: 5}
one.Next = &two
two.Next = &three
three.Next = &four
four.Next = &five
node := reverseList(&one)
readNode(node)
}
4.合并两个有序链表
题目：合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [0]
输出：[0]
答案：
//链表遍历。利用额外一个头结点，解决该问题
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
head := &ListNode{}
cur := head
for list1 != nil || list2 != nil {
if list1 != nil && list2 != nil {
if list1.Val < list2.Val {
cur.Next = list1
list1 = list1.Next
} else {
cur.Next = list2
list2 = list2.Next
}
cur = cur.Next
} else if list2 == nil {
cur.Next = list1
break
} else if list1 == nil {
cur.Next = list2
break
}
}
return head.Next
}
func main() {
one := ListNode{Val: 1}
two := ListNode{Val: 2}
three := ListNode{Val: 3}
four := ListNode{Val: 4}
five := ListNode{Val: 5}
six := ListNode{Val: 6}
one.Next = &three
three.Next = &five
two.Next = &four
four.Next = &six
node := mergeTwoLists(&one, &two)
readNode(node)
}
func readNode(node *ListNode) {
for {
if node != nil {
fmt.Println(node.Val)
node = node.Next
} else {
break
}
}
}
type ListNode struct {
Val int
Next *ListNode
}
5.判断回文链表
题目：回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
答案：
/*
解析：循环链表，把链表中的所有值加入到切片，然后判断切片是否位回文
*/
func isPalindrome(head *ListNode) bool {
li := []int{}
for head != nil {
li = append(li, head.Val)
head = head.Next
}
for k := range li {
if li[k] != li[len(li)-k-1] {
return false
}
}
return true
}
func main() {
one := ListNode{Val: 1}
one2 := ListNode{Val: 1}
three := ListNode{Val: 3}
three2 := ListNode{Val: 3}
one.Next = &three
three.Next = &three2
three2.Next = &one2
fmt.Println(isPalindrome(&one))
}
6.判断是否为环形链表
题目：环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
示例 1:
输入：1->2->3->2->3->2
输出：true
示例 1:
输入：1->2->3
输出：false
答案：
/*
解析：借助map，把每一个节点的地址存起来。然后每查找一个节点，map中查询，如果查到了证明是环形节点
*/
func hasCycle(head *ListNode) bool {
dic := make(map[*ListNode]struct{})
for head != nil {
_, ok := dic[head]
if ok {
return true
}
dic[head] = struct{}{}
head = head.Next
}
return false
}
func main() {
one := ListNode{Val: 1}
two := ListNode{Val: 2}
three := ListNode{Val: 3}
four := ListNode{Val: 4}
//five := ListNode{Val: 5}
//six := ListNode{Val: 6}
one.Next = &two
two.Next = &three
three.Next = &four
four.Next = &two
fmt.Println(hasCycle(&one))
}