leetcode链表必刷题——移除链表元素、设计链表、反转链表、两两交换链表中的节点、删除链表的倒数第 N 个结点、相交链表、环形链表、环形链表 II

文章目录

  • 移除链表元素
  • 设计链表
  • 反转链表
  • 两两交换链表中的节点
  • 删除链表的倒数第 N 个结点
  • 相交链表
  • 环形链表
  • 环形链表 II

移除链表元素

题目链接

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

img

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

Python：

#本人解法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if head is None:
            return None
        a = []
        while head:
            if head.val != val:
                a.append(head)
            head = head.next
        l = len(a)
        if l == 0:
            return None
        for i in range(l - 1):
            a[i].next = a[i + 1]
        a[l - 1].next = None
        return a[0]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if head is None:
            return None
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head
# 链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求
# 删除链表中所有节点值等于特定值的节点，可以用递归实现。对于给定的链表，
# 首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值
# 是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，
# 因此删除操作后的头节点为 head.next;如果 head 的节点值不等于 val，
# 则 head 保留，因此删除操作后的头节点还是 head。上述过程是一个递归的过程。
# 递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，
# 递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。

# 迭代
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy_head = ListNode(0, head)
        cur = dummy_head
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

Go：

//本人解法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
	if head == nil {
		return nil
	}
	var a []*ListNode
	for head != nil {
		if head.Val != val {
			a = append(a, head)
		}
		head = head.Next
	}
	l := len(a)
	if l == 0 {
		return nil
	}
	for i := 0; i < l-1; i++ {
		a[i].Next = a[i+1]
	}
	a[l-1].Next = nil
	return a[0]
}

//递归
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
	if head == nil {
		return head
	}
	head.Next = removeElements(head.Next, val)
	if head.Val == val {
		return head.Next
	} else {
		return head
	}
}

/*
链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。这道题要求  删除链表中所有节点值等于特定值的节点，可以用递归实现。对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next;如果 head 的节点值不等于 val，则 head 保留，因此删除操作后的头节点还是 head。上述过程是一个递归的过程。递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
*/

//迭代
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeElements(head *ListNode, val int) *ListNode {
	dummyHead := &ListNode{Next: head}
	for tmp := dummyHead; tmp.Next != nil; {
		if tmp.Next.Val == val {
			tmp.Next = tmp.Next.Next
		} else {
			tmp = tmp.Next
		}
	}
	return dummyHead.Next
}

设计链表

题目链接

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

  • 0 <= index, val <= 1000
  • 请不要使用内置的 LinkedList 库。
  • 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

Python：

# class ListNode:
#     def __init__(self, val):
#         self.val = val
#         self.next = None

class MyLinkedList:
    def __init__(self):
        self.size = 0
        self.head = ListNode(0)

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        cur = self.head
        for _ in range(index + 1):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)
        return

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)
        return

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        self.size += 1
        index = max(0, index)
        cur = self.head
        for _ in range(index):
            cur = cur.next
        add = ListNode(val)
        add.next = cur.next
        cur.next = add
        return

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        cur = self.head
        for _ in range(index):
            cur = cur.next
        cur.next = cur.next.next
        return


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

Go：

// type ListNode struct {
// 	Val  int
// 	Next *ListNode
// }

type MyLinkedList struct {
    head *ListNode
    size int
}

func Constructor() MyLinkedList {
    return MyLinkedList{&ListNode{}, 0}
}

func (l *MyLinkedList) Get(index int) int {
    if index < 0 || index >= l.size {
        return -1
    }
    cur := l.head
    for i := 0; i <= index; i++ {
        cur = cur.Next
    }
    return cur.Val
}

func (l *MyLinkedList) AddAtHead(val int) {
    l.AddAtIndex(0, val)
}

func (l *MyLinkedList) AddAtTail(val int) {
    l.AddAtIndex(l.size, val)
}

func (l *MyLinkedList) AddAtIndex(index, val int) {
    if index > l.size {
        return
    }
    index = max(index, 0)
    l.size++
    pred := l.head
    for i := 0; i < index; i++ {
        pred = pred.Next
    }
    toAdd := &ListNode{val, pred.Next}
    pred.Next = toAdd
}

func (l *MyLinkedList) DeleteAtIndex(index int) {
    if index < 0 || index >= l.size {
        return
    }
    l.size--
    pred := l.head
    for i := 0; i < index; i++ {
        pred = pred.Next
    }
    pred.Next = pred.Next.Next
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}


/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Get(index);
 * obj.AddAtHead(val);
 * obj.AddAtTail(val);
 * obj.AddAtIndex(index,val);
 * obj.DeleteAtIndex(index);
 */

反转链表

题目链接

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

Python：

#本人解法
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        a = []
        if head is None:
            return None
        while head:
            a.append(head)
            head = head.next
        for i in range(len(a) - 1, 0, -1):
            a[i].next = a[i - 1]
        a[0].next = None
        return a[-1]

#迭代解法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

Go：

//本人解法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
	var a []*ListNode
	if head == nil {
		return nil
	}
	for head != nil {
		a = append(a, head)
		head = head.Next
	}
	for i := len(a) - 1; i > 0; i-- {
		a[i].Next = a[i-1]
	}
	a[0].Next = nil
	return a[len(a)-1]
}

//官方解法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    return prev
}

两两交换链表中的节点

题目链接

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

swap_ex1

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

Python：

# 递归法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        newHead = head.next
        head.next = self.swapPairs(newHead.next)
        newHead.next = head
        return newHead

# 迭代法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(0, head)
        tmp = dummy_head
        while tmp.next and tmp.next.next:
            node1 = tmp.next
            node2 = node1.next
            tmp.next = node2
            node1.next = node2.next
            node2.next = node1
            tmp=node1
        return dummy_head.next

Go：

//递归法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := head.Next
	head.Next = swapPairs(newHead.Next)
	newHead.Next = head
	return newHead
}

//迭代法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    dummyHead := &ListNode{0, head}
    temp := dummyHead
    for temp.Next != nil && temp.Next.Next != nil {
        node1 := temp.Next
        node2 := temp.Next.Next
        temp.Next = node2
        node1.Next = node2.Next
        node2.Next = node1
        temp = node1
    }
    return dummyHead.Next
}

删除链表的倒数第 N 个结点

题目链接

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

image-20231115162022904

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Python：

# 虚拟头结点
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        k = -1
        dummy_head = ListNode(0, head)
        tmp = dummy_head
        while tmp:
            k += 1
            tmp = tmp.next
        tmp = dummy_head
        for i in range(k - n):
            tmp = tmp.next
        tmp.next = tmp.next.next
        return dummy_head.next

# 双指针法(对称)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        first = head
        second = dummy
        for i in range(n):
            first = first.next

        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next
        return dummy.next

# 列表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        nodes = []
        dummy = ListNode(0, head)
        node = dummy
        while node:
            nodes.append(node)
            node = node.next
        prev = nodes[len(nodes) - 1 - n]
        prev.next = prev.next.next
        return dummy.next

# 列表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        a = []
        while head:
            a.append(head)
            head = head.next
        a.pop(len(a) - n)
        for i in range(len(a) - 1):
            a[i].next = a[i + 1]
        if len(a) == 0:
            return None
        a[len(a) - 1].next = None
        return a[0]

Go：

//使用虚拟头结点
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	k := -1
	dummyHead := &ListNode{0, head}
	for tmp := dummyHead; tmp != nil; tmp = tmp.Next {
		k++
	}
	tmp := dummyHead
	for i := 0; i < k-n; i++ {
		tmp = tmp.Next
	}
	tmp.Next = tmp.Next.Next
	return dummyHead.Next
}

// 双指针法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head}
    first, second := head, dummy
    for i := 0; i < n; i++ {
        first = first.Next
    }
    for ; first != nil; first = first.Next {
        second = second.Next
    }
    second.Next = second.Next.Next
    return dummy.Next
}

//数组
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    nodes := make([]*ListNode, 0)
    dummy := &ListNode{0, head}
    for node := dummy; node != nil; node = node.Next {
        nodes = append(nodes, node)
    }
    prev := nodes[len(nodes)-1-n]
    prev.Next = prev.Next.Next
    return dummy.Next
}

//数组
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	a := make([]*ListNode, 0)
	for head != nil {
		a = append(a, head)
		head = head.Next
	}
	a = append(a[:len(a)-n], a[len(a)-n+1:]...)
	for i := 0; i < len(a)-1; i++ {
		a[i].Next = a[i+1]
	}
	if len(a) == 0 {
		return nil
	}
	a[len(a)-1].Next = nil
	return a[0]
}

相交链表

题目链接

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

Python：

# 哈希表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        hash_map = {}
        curr = headA
        while curr:
            hash_map[curr] = True
            curr = curr.next

        curr = headB
        while curr:
            if curr in hash_map:
                return curr
            curr = curr.next

        return None


#双指针
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        A, B = headA, headB
        while A != B:
            A = A.next if A else headB
            B = B.next if B else headA
        return A

# 数组(耗时高,不推荐)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        arr=[]
        curr = headA
        while curr:
            arr.append(curr)
            curr = curr.next

        curr = headB
        while curr:
            if curr in arr:
                return curr
            curr = curr.next

        return None

Go：

//哈希表
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    vis := map[*ListNode]bool{}
    for tmp := headA; tmp != nil; tmp = tmp.Next {
        vis[tmp] = true
    }
    for tmp := headB; tmp != nil; tmp = tmp.Next {
        if vis[tmp] {
            return tmp
        }
    }
    return nil
}

//双指针
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    a, b := headA, headB
	for a != b {
		if a != nil {
			a = a.Next
		} else {
			a = headB
		}
		if b != nil {
			b = b.Next
		} else {
			b = headA
		}
	}
	return a
}

//数组(耗时高，不推荐)
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	var vis []*ListNode
	for tmp := headA; tmp != nil; tmp = tmp.Next {
		vis = append(vis, tmp)
	}
	for tmp := headB; tmp != nil; tmp = tmp.Next {
		for i := 0; i < len(vis); i++ {
			if tmp == vis[i] {
				return tmp
			}
		}
	}
	return nil
}

环形链表

题目链接

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

image-20231116131946732

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

image-20231116132004857

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

image-20231116132014318

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -10^5 <= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个 有效索引 。

Python：

# 内存少
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        num = 10**5 + 1
        tmp = head
        while tmp:
            if tmp.val == num:
                return True
            else:
                tmp.val = num
            tmp = tmp.next
        return False
        

# 哈希表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        vis = {}
        tmp = head
        while tmp:
            if tmp not in vis.keys():
                vis[tmp] = True
            else:
                return True
            tmp = tmp.next
        return False

# 双指针法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head  # 乌龟和兔子同时从起点出发
        while fast and fast.next:
            slow = slow.next  # 乌龟走一步
            fast = fast.next.next  # 兔子走两步
            if fast is slow:  # 兔子追上乌龟（套圈），说明有环
                return True
        return False  # 访问到了链表末尾，无环
# 兔子会不会「跳过」乌龟，从来不会和乌龟相遇呢？
# 这是不可能的。如果有环的话，那么兔子和乌龟都会进入环中。这时用「相对速度」思考，乌龟不动，兔子相对乌龟每次只走一步，这样就可以看出兔子一定会和乌龟相遇了。

Go：

//内存少
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

import "math"

func hasCycle(head *ListNode) bool {
	num := int(math.Pow(10, 5) + 1)
	for tmp := head; tmp != nil; tmp = tmp.Next {
		if tmp.Val == num {
			return true
		} else {
			tmp.Val = num
		}
	}
	return false
}

//哈希表
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func hasCycle(head *ListNode) bool {
	vis := make(map[*ListNode]bool)
	for tmp := head; tmp != nil; tmp = tmp.Next {
		if ok := vis[tmp]; !ok {
			vis[tmp] = true
		} else {
			return true
		}
	}
	return false
}

// 双指针法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func hasCycle(head *ListNode) bool {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			return true
		}
	}
	return false
}

环形链表 II

题目链接

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

image-20231116131946732

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

image-20231116132004857

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

image-20231116132014318

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

Python：

# 本人解法
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        num = 10**5 + 1
        tmp = head
        while tmp:
            if tmp.val == num:
                return tmp
            else:
                tmp.val = num
            tmp = tmp.next
        return None

# 哈希表
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vis = {}
        tmp = head
        while tmp:
            if tmp not in vis.keys():
                vis[tmp] = True
            else:
                return tmp
            tmp = tmp.next
        return None

# 双指针法，其实就将这道题变成了数学题
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                while slow is not head:
                    slow = slow.next
                    head = head.next
                return slow
        return None

Go：

//本人解法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 import "math"
 
func detectCycle(head *ListNode) *ListNode {
	num := int(math.Pow(10, 5) + 1)
	for tmp := head; tmp != nil; tmp = tmp.Next {
		if tmp.Val == num {
			return tmp
		} else {
			tmp.Val = num
		}
	}
	return nil
}

//哈希表
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 func detectCycle(head *ListNode) *ListNode {
	vis := make(map[*ListNode]bool)
	for tmp := head; tmp != nil; tmp = tmp.Next {
		if ok := vis[tmp]; !ok {
			vis[tmp] = true
		} else {
			return tmp
		}
	}
	return nil
}

//双指针法
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if fast == slow {
			for slow != head {
				slow = slow.Next
				head = head.Next
			}
			return slow
		}
	}
	return nil
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/152862.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

1分钟精准预测未来10天天气，谷歌开源GraphCast

1分钟精准预测未来10天天气，谷歌开源GraphCast

11月15日&#xff0c;谷歌旗下著名AI研究机构Deepmind在官网宣布&#xff0c;开源天气大模型GraphCast&#xff0c;并公布了论文。 据悉&#xff0c;GraphCast可以在1分钟内&#xff0c;精准预测而来全球10天的天气情况&#xff0c;同时可以提前预警大暴雨、大风雪、洪水、高温…
阅读更多...
KeyarchOS的CentOS迁移实践：使用操作系统迁移工具X2Keyarch V2.0

KeyarchOS的CentOS迁移实践：使用操作系统迁移工具X2Keyarch V2.0

KeyarchOS的CentOS迁移实践&#xff1a;使用操作系统迁移工具X2Keyarch V2.0 作者&#xff1a; 猫头虎博主 文章目录 KeyarchOS的CentOS迁移实践&#xff1a;使用操作系统迁移工具X2Keyarch V2.0&#x1f405;摘要引言1. 迁移前的精心准备1.1 系统环境介绍1.2 深度数据验证1.2.…
阅读更多...
语音识别芯片NRK3301在智能茶吧机的应用

语音识别芯片NRK3301在智能茶吧机的应用

传统的饮水机传大多只能提供热水和冷水&#xff0c;而智能茶吧机则是一款集合了热饮水机、煮茶器、泡茶壶等多种功能于一体的多功能生活电器。它不仅具备了传统饮水机的所有功能&#xff0c;还可以根据不同的需求&#xff0c;提供多种水温的饮水方式&#xff1b;还具备了煮茶和…
阅读更多...
Cesium+Vue：地形开挖

Cesium+Vue：地形开挖

作者：CSDN @ _乐多_ 本文记录了在Cesium中进行地形开挖的方法和代码。使用Vue框架。 效果如下所示， 文章目录 前言：配置Cesium一、Vue文件二、创建地形开挖函数库三、创建绘制图形库四、创建提示语库前言：配置Cesium 参考《Vue：Vue项目中的Cesium配置备忘录》
阅读更多...
【搭建私人图床】使用LightPicture开源搭建图片管理系统并远程访问

【搭建私人图床】使用LightPicture开源搭建图片管理系统并远程访问

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进&#xff0c;功能也越来越多&#xff0c;而手机…
阅读更多...
安装PostgreSql 9.6版本报错

安装PostgreSql 9.6版本报错

先去官网&#xff1a;Community DL Page 下载了一个“9.6.24*”版本的PostgreSql&#xff0c;然后开始安装。 安装PostgreSql 报错&#xff1a; Cant install PostgreSQL: An error occurred executing the Microsoft VC runtime installer 第一&#xff0c;先&#xff1a;右…
阅读更多...
外汇天眼：「外汇回撤」这术语是指什么？

外汇天眼：「外汇回撤」这术语是指什么？

"外汇回撤"是外汇交易中一个常见的专业术语。对于许多投资者&#xff0c;尤其是初学者来说&#xff0c;可能并不十分理解这个术语的实质。下面我们将详细介绍外汇回撤的含义。 外汇回撤通常被称为"外汇百分比回撤"。在外汇市场出现强烈趋势波动时&#xf…
阅读更多...
Python自动化测试之request库详解（三）

Python自动化测试之request库详解（三）

做过接口测试的都会发现&#xff0c;现在的接口都是HTTPS协议了&#xff0c;今天就写一篇如何通过request发送https请求。 什么是HTTPS HTTPS 的全称是Hyper Text Transfer Protocol over Secure Socket Layer &#xff0c;是以安全为目标的HTTP通道&#xff0c;简单的讲是HTT…
阅读更多...
UI游戏设计模板大放送：7种别具匠心的创意！

UI游戏设计模板大放送：7种别具匠心的创意！

随着游戏产业的快速发展&#xff0c;UI游戏设计已经成为一个热门的设计行业&#xff0c;但与之前的设计相比&#xff0c;UI游戏设计还是比较特殊的&#xff0c;主要体现在UI游戏设计难度大&#xff0c;需要大量的手绘内容和对游戏玩法的理解上。这些门槛需要大量的时间去学习&a…
阅读更多...
ALlegro怎么恢复到初始操作界面？

ALlegro怎么恢复到初始操作界面？

1.View 2.UI Settings 3.Reset UI To Default
阅读更多...
Python winreg将cmd/PowerShell（管理员）添加到右键菜单

Python winreg将cmd/PowerShell（管理员）添加到右键菜单

效果 1. 脚本 用管理员权限运行&#xff0c;重复执行会起到覆盖效果&#xff08;根据sub_key&#xff09;。 icon自己设置。text可以自定义。sub_key可以改但不推荐&#xff08;避免改成和系统已有项冲突的&#xff09;。command不要改。 from winreg import *registry r&q…
阅读更多...
【小黑送书—第七期】＞＞程序员To架构师？一起来看架构师系列书籍推荐

【小黑送书—第七期】＞＞程序员To架构师？一起来看架构师系列书籍推荐

相信大家都对未来的职业发展有着憧憬和规划&#xff0c;要做架构师、要做技术总监、要做CTO。对于如何实现自己的职业规划也都信心满满&#xff0c;努力工作、好好学习、不断提升自己。 相信成为一名优秀的架构师是很多程序员的目标&#xff0c;架构师的工作包罗万象&#xff…
阅读更多...
web前端开发网页设计课堂作业/html练习《课程表》

web前端开发网页设计课堂作业/html练习《课程表》

目标图&#xff1a; 运行代码&#xff1a; <head> <meta http-equiv"Content-Type" content"text/html; charsetutf-8" /> <title>无标题文档</title><body> <table border"3" align"center"> &…
阅读更多...
Python 搭建虚拟环境

Python 搭建虚拟环境

一、虚拟环境简介 虚拟环境virtual environment&#xff0c;它是一个虚拟化&#xff0c;从电脑独立开辟出来的环境。通俗的来讲&#xff0c;虚拟环境就是借助虚拟机来把一部分内容独立出来&#xff0c;我们把这部分独立出来的东西称作“容器”&#xff0c;在这个容器中&#xf…
阅读更多...
Android——gradle构建知识片-散装版

Android——gradle构建知识片-散装版

一、Gradle - Plugins插件库地址 Gradle - Plugins插件库地址https://plugins.gradle.org/ 二、将自己的代码Android Library发布到仓库Bintray、JCenter、JitPack 放弃JitPack&#xff0c;发布Android Library到Bintray、JCenter - 简书Bug&#xff1a;升级到gradle tools …
阅读更多...
黑马天机学堂-2、我的课程表 接口分析与设计

黑马天机学堂-2、我的课程表 接口分析与设计

在昨天的学习中&#xff0c;我带领大家解决了天机学堂的简单的BUG。并且演示了整个项目的核心业务流程。现在&#xff0c;你对项目有了基本的了解&#xff0c;是时候动手开发一些业务功能了。 接下来接收到一个正式的开发任务&#xff1a;开发天机学堂项目的学习辅助相关功能。…
阅读更多...
人工智能基础_机器学习040_Sigmoid函数详解_单位阶跃函数与对数几率函数_伯努利分布---人工智能工作笔记0080

人工智能基础_机器学习040_Sigmoid函数详解_单位阶跃函数与对数几率函数_伯努利分布---人工智能工作笔记0080

然后我们再来详细说一下Sigmoid函数,上面的函数的公式 我们要知道这里的,Sigmoid函数的意义,这逻辑斯蒂回归的意义就是,在多元线性回归的基础上,把 多元线性回归的结果,缩放到0到1之间对吧,根据中间的0.5为分类,小于0.5的一类,大于的一类, 这里的h theta(x) 就是概率函数 然…
阅读更多...
Nginx配置免费HTTPS详细教程

Nginx配置免费HTTPS详细教程

文章目录 背景说明环境准备说明安装Nginx及依赖环境配置HTTPS步骤步骤1&#xff1a;创建服务器私钥步骤2&#xff1a;创建签名请求的证书&#xff08;CSR&#xff09;步骤3&#xff1a;加载SSL支持的Nginx并使用私钥时去除口令步骤4&#xff1a;将密钥文件移动到Nginx配置文件目…
阅读更多...
【每日一题】2760. 最长奇偶子数组-2023.11.16

【每日一题】2760. 最长奇偶子数组-2023.11.16

题目&#xff1a; 2760. 最长奇偶子数组 给你一个下标从 0 开始的整数数组 nums 和一个整数 threshold 。 请你从 nums 的子数组中找出以下标 l 开头、下标 r 结尾 (0 < l < r < nums.length) 且满足以下条件的 最长子数组 &#xff1a; nums[l] % 2 0对于范围 […
阅读更多...
MyEclipse 2017 安装与pj

MyEclipse 2017 安装与pj

关于Myeclipse 2017的安装与破解 MyEclipse企业级工作平台&#xff08;MyEclipseEnterprise Workbench &#xff0c;简称MyEclipse&#xff09;是对EclipseIDE的扩展&#xff0c;利用它我们可以在数据库和JavaEE的开发、发布以及应用程序服务器的整合方面极大的提高工作效率。…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站