首页 > 其他分享 >leetcode链表1-6

leetcode链表1-6

时间:2022-09-29 17:56:37浏览次数:42  
标签:head ListNode Val leetcode 链表 Next 节点

目录

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

标签:head,ListNode,Val,leetcode,链表,Next,节点
From: https://www.cnblogs.com/guyouyin123/p/16742448.html

相关文章

  • LeetCode 2296. Design a Text Editor
    原题链接在这里:https://leetcode.com/problems/design-a-text-editor/题目:Designatexteditorwithacursorthatcandothefollowing:Add texttowherethecu......
  • leetcode169-多数元素
    169.多数元素这道题虽然是简单题,但是有很多精妙的解法。详情看官方题解classSolution{public:intmajorityElement(vector<int>&nums){intsize=n......
  • leetcode -- tree 2
    最大二叉树递归构造classSolution:defconstructMaximumBinaryTree(self,nums:List[int])->Optional[TreeNode]:ifnotnums:retur......
  • 单链表注意事项
    经常采用的方法有头插法、尾插法、逆置法、归并法、双指针法等,对具体问题需要灵活变通;对于顺序表,由于可以直接存取,经常结合排序和查找的几种算法设计思路进行设计,如归并排......
  • LeetCode[3] 无重复字符的最长子串
    1无重复字符的最长子串1.1题目描述        给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。示例 1:输入:s="abcabcbb"输出:3解释:......
  • 循环链表(约瑟夫环)思路及实现
    循环链表单链表的尾节点指向首节点,即可构成循环链表约瑟夫环约瑟夫问题:有N个人围成一圈,每个人都有一个编号,编号由入圈的顺序决定,第一个入圈的人编号为1,最后一个为N......
  • LeetCode[13] 罗马数字转整数
    1罗马数转整数1.1题目描述        罗马数字包含以下七种字符: I, V, X, ``L,C,D 和 M`。字符数值I1V5X10L50C100D500M100......
  • golang 的双向循环链表
                如下为go实现的双向循环列表。packagemainimport("fmt")typeRingstruct{prev,......
  • leetcode977-有序数组的平方
    977.有序数组的平方原本直接暴力的做法没有利用到原数组是有序这个条件。这里直接把左边的绝对值大于右边的直接放到最后面,这样就减少很多不必要的操作。classSoluti......
  • 开着想象中的小汽车来了,leetcode刷题开始
    想去德国留学和工作,因为没去过欧美国家,所以有点好奇,想趁年轻且单身的时候多出去看看。德国大学的话,印象中是免学费的,如果要继续提升学历的话,就要去读博啦,目前毫无头绪,家里......