链表

定义

一种在物理上非连续、非顺序的数据结构，由若干个节点组成。

题目

反装链表

https://leetcode.cn/problems/reverse-linked-list/

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

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

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var prev, tmp *ListNode
    for head != nil {
        tmp = head.Next
        head.Next = prev
        prev = head
        head = tmp
    }
    return prev
}

K 个一组翻转链表

https://leetcode.cn/problems/reverse-nodes-in-k-group/

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {

}

两两交换链表中的节点

https://leetcode.cn/problems/swap-nodes-in-pairs/

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

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    // 设置虚拟结点 dummy，因为真实头结点会变，设置了 dummy ，头结点就是 dummy.Next
    dummy := &ListNode{Next: head}
    prev := dummy

    // 遍历
    for head != nil && head.Next != nil {
        // 存储下 next，为了区分防止眼花我们设置为 tmp
        tmp := head.Next
        // head.Next = next.Next
        head.Next = tmp.Next
        // next.Next = head
        tmp.Next = head
        // head.Next = next.Next 也就是上面的 tmp
        prev.Next = tmp

        prev = head
        head = head.Next
    }

    // 返回头结点
    return dummy.Next
}

环形链表

https://leetcode.cn/problems/linked-list-cycle/

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

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

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

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
// 使用 map
func hasCycle(head *ListNode) bool {
    hash :=  make(map[*ListNode]bool)

    for head != nil {
        if hash[head] {
            return true
        } 

        hash[head] = true

        head = head.Next
    }

    return false
}

// 快慢指针
func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    fast := head.Next
    for fast != nil && fast.Next != nil {
        if fast == head {
            return true
        }

        head, fast = head.Next, fast.Next.Next
    }

    return false
}

环形链表2

https://leetcode.cn/problems/linked-list-cycle-ii/

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

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

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

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

这题比较难得是找出入环的那个 node

func detectCycle(head *ListNode) *ListNode {
    hash := map[*ListNode]bool
    for head != nil {
        if _, ok := hash[head]; ok {
            return head
        }
        hash[head] = true
        head = head.Next
    }
    return nil
}


func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next ==  nil {
        return nil
    }

    slow, fast := head.Next, head.Next.Next
    for fast != nil && fast.Next != nil {
        if slow == fast {
            fast = head
            for fast != slow {
                fast, slow = fast.Next, slow.Next
            }

            return slow
        }
        slow, fast = slow.Next, fast.Next.Next
    }


    return nil
}

关注和赞赏都是对小欧莫大的支持！ 🤝 🤝 🤝
公众号

← kubectl
镜像 →