• 链表入门推荐

    链表

    说明：

    你可以打印出来，平时没事复习，看看

    学习来源：https://greyireland.gitbook.io/algorithm-pattern/shu-ju-jie-gou-pian/linked_list

    用的人家的思路，题解自己写，算是对其补充，也算是打卡

    基本技能

    链表相关的核心点

    • null/nil 异常处理
    • dummy node 哑巴节点
    • 快慢指针
    • 插入一个节点到排序链表
    • 从一个链表中移除一个节点
    • 翻转链表
    • 合并两个链表
    • 找到链表的中间节点
    1、83. 删除排序链表中的重复元素-简单

    给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

    请添加图片描述

    go虽然是值传递，但是链表用到了指针，传递的是一个地址，所以这种情况下可以说是址传递

    /**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    current := head // 把头节点给current，代表当前节点
    for current != nil { // 当前节点不为空
        // 当下一个节点不为空，且当前节点的值等于下一个节点的值时候，把下一个节点替换为下下一个节点，简单说就是删除下一个节点，
        for current.Next != nil && current.Val == current.Next.Val { 
            current.Next = current.Next.Next
        }
        current = current.Next // 使其移动到下一个节点，继续删除多余元素    使当前节点为空，跳出循环
    }
    return head
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    2、82. 删除排序链表中的重复元素 II-中等

    给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

    请添加图片描述

    注意区分和83题，这一题要的是删除所有的只要是重复过的，举例出现了三个1，都删掉，83题是重复的删除，留一个，三个1删除两个留一个1

    用到了虚拟节点dummy

    func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    // 使用虚拟节点是因为节点头可能被删除，一旦节点头被删除就不好找到head这个链表了
    dummy := &ListNode{Val: 0}
    dummy.Next = head
    headr := dummy // 这一步不要迷哈，上一步head已经完成了任务，把链表接给了dummy，所以head一身轻了，可以作为一个自由变量，如果不习惯的话，可以把代码中这一行以下的所有的head全都换一个名字

    var rmVal int
    for headr.Next != nil && headr.Next.Next != nil {
       if headr.Next.Val == headr.Next.Next.Val {
           rmVal = headr.Next.Val // 记录要删除的节点的值
           for headr.Next != nil && headr.Next.Val == rmVal {
               headr.Next = headr.Next.Next
           }
       } else {
           // 删除完所有一样的元素后，去掉虚拟节点
           headr = headr.Next
       }
    }
    return dummy.Next
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    3、206. 反转链表-简单

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

    请添加图片描述

    总结一下，这次带入例子思考的理解的特别慢，指针方向变了，我没理解，不过看了Carl的图解，一下就理解了

    func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        // next = 2,3,4,5
        // cur接上pre
        // pre = cur,反转指针方向
        // cur = next 进入下一层
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    4、92. 反转链表 II-中等

    给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

    请添加图片描述

    这一题看不懂…

    思路:

    1. 判断head为空，返回head，就是nil
    2. 设置虚拟节点dummy，连接起来
    3. 设置pre，作为为最后成功的结果，结果发现不对，差了点
    4. 通过for循环把head推到left位置
    5. 接着就是咱们的经典四步了
    6. 通过mid中间节点连接就可以了
    /**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    if head == nil {
        return head
    }
    dummy := &ListNode{Val:0}
    dummy.Next = head
    head = dummy
    // head变成了 0->1->2->3->4->5->nil
    var pre *ListNode
    var i = 0
    for i < left {
        pre = head
        head = head.Next
        i++
    }
    // 链表变成了1(pre)->2(head)->3->4->5->nil
    // i = 1
    var next *ListNode
    for head != nil && i <= right {
        // 经典四步（双指针法）+ j++
        temp := head.Next
        head.Next = next
        next = head
        head = temp
        i++
    }
    // 用于中间节点连接
    var mid = head
    // 循环结束变成 1 nil<-2<-3<-4 5(head)->nil
    pre.Next = next // pre变成了1->4->3->2-nil
    mid.Next = head // 1->4->3->2-5->nil
    return dummy.Next
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    5、21. 合并两个有序链表-简单

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    请添加图片描述

    1. 给个虚拟节点
    2. 判断谁小，就赋值给head.Next,谁就推到下一个节点，接着head推到下一个节点
    3. 完了肯定会l1或l2或l1和l2都为空了，如果某个不为空，就全给head
    func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    head := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            head.Next = l1
            l1 = l1.Next
        } else {
            head.Next = l2
            l2 = l2.Next
        }
        head = head.Next
    }
    // 不要像是pattern给的代码一样，一个节点一个节点的给的....这个不太理解，他是指针，一个一个给的话，浪费资源
    if l1 != nil {
        head.Next = l1
    }
    if l2 != nil {
        head.Next = l2
    }
    return dummy.Next
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    6、86. 分隔链表-中等

    给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

    你应当 保留 两个分区中每个节点的初始相对位置。

    请添加图片描述

    思路:

    1. 好好读题

    2. 整两个链表，最后拼接在一起

    3. 好好思考一下dummy的妙用

    func partition(head *ListNode, x int) *ListNode {
    // 直接判断在x后边的元素是否有小于x的，就放在大于或等于x的节点的前面
    if head == nil {
        return head
    }
    headDummy := &ListNode{Val: 0}
    tailDummy := &ListNode{Val: 0}
    tail := tailDummy 
    // tail就是相当于tailcur，是当前的意思，节点会向下移动，tailDummy就是这个链表头节点，head同样道理
    headDummy.Next = head
    head = headDummy // 等于是给head加了一个前节点0,思考一下为什么要加一个虚拟头节点
    for head.Next != nil {
        if head.Next.Val < x {
            head = head.Next
        } else {
            t := head.Next // 移除前保存这个值
            head.Next = head.Next.Next // 移除
            // 把t给另一个链表tail
            tail.Next = t
            tail = tail.Next
        }
    }
    // 拼接两个链表
    tail.Next = nil
    head.Next = tailDummy.Next
    return headDummy.Next
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    7、148. 排序链表-中等

    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

    请添加图片描述

    1. 十大排序算法之第一种,但是可能会超时
    2. 咱们归并排序，找到中点，模拟，之前有个题目就是升序合并
    3. 归并排序，dfs算法
    func sortList(head *ListNode) *ListNode {
    return mergeSort(head)
}
// 快慢指针找中间的节点
func findMiddle(head *ListNode) *ListNode {
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}
// 合并两个升序链表
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    head := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            head.Next = l1
            l1 = l1.Next
        } else {
            head.Next = l2
            l2 = l2.Next
        }
        head = head.Next // 这一步不要忘了，当前head有了节点后指向下一个
    }
    if l1 != nil {
        head.Next = l1
    }
    if l2 != nil {
        head.Next = l2
    }
    return dummy.Next
}
func mergeSort(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 找中点，分割，合并
    middle := findMiddle(head)
    tail := middle.Next
    middle.Next = nil
    // dfs算法思想，找到最小子问题，递归
    left := mergeSort(head)
    right := mergeSort(tail)
    res := mergeTwoLists(left, right)
    return res
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    8、143. 重排链表-中等
    给定一个单链表 `L` 的头节点 `head` ，单链表 `L` 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    判断head为nil，和head.Next为nil情况直接返回
    找中点，分割链表
    反转后边的链表tail
    改写合并两个升序链表为交叉合并，判断条件变为判断toggle的情况

    func reorderList(head *ListNode)  {
    if head == nil || head.Next == nil{
        return
    }
    middle := findMiddle(head)
    tail := middle.Next
    tail = reverseList(tail)
    middle.Next = nil
    head = mergeTwoList(head,tail)
}
// 快慢指针找中点
func findMiddle(head *ListNode) *ListNode {
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}
// 循环合并两个链表
func mergeTwoList(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    head := dummy
    toggle := true
    for l1 != nil && l2 != nil {
        if toggle {
            head.Next = l1
            l1 = l1.Next
        } else {
            head.Next = l2
            l2 = l2.Next
        }
        toggle = !toggle
        head = head.Next
    }
    if l1 != nil {
        head.Next = l1
    }
    if l2 != nil {
        head.Next = l2
    }
    return dummy.Next
}
// 反转后半段的新链表，反转链表经典四步
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    for head != nil {
        cur := head.Next
        head.Next = pre
        pre = head
        head = cur
    }
    return pre
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    9、141. 环形链表-简单

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

    利用快慢指针会造成差距越来越大的特性，如果有环，走完之后，快指针每次循环以一个单位的速度追到慢指针

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    10、142. 环形链表 II-中等

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

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

    不允许修改 链表。

    请添加图片描述

    func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    // 还是快慢指针法
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            slow = slow.Next
            fast = head
            for slow != fast {
                slow = slow.Next
                fast = fast.Next
            }
            return slow
        }
    }
    return nil
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    11、234. 回文链表-简单

    给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

    请添加图片描述

    思路

    1. 由链表的几个基本技巧组合而解决
    2. 分割链表，反转链表，然后for比对即可

    自己写出来的，开心…不过是简单题

    func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }
    // 快慢节点，分割
    mid := middle(head)
    // 反转链表
    tail := reverseList(mid.Next)
    mid.Next = nil
    // 比对
    for head != nil && tail != nil {
        if head.Val != tail.Val{
            return false
        }
        head = head.Next
        tail = tail.Next
    }
    return true
}
func middle(head *ListNode) *ListNode {
    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    // 经典四步法
    var pre *ListNode
    for head != nil {
        cur := head.Next
        head.Next = pre
        pre = head
        head = cur
    }
    return pre
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    12、138. 复制带随机指针的链表-中等

    给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

    构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

    例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

    返回复制链表的头节点。

    请添加图片描述

    1. 判断为空，直接返回
    2. 复制正常链表
    3. 复制random指针
    4. 分割链表
    /**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    cur := head
    for cur != nil {
        // 像极了反转链表的经典四步
        clone := &Node{Val: cur.Val, Next: cur.Next}
        temp := cur.Next
        cur.Next = clone
        cur = temp
    }
    // 处理random指针
    cur = head
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }
    // 分割两个链表
    cur = head
    cloneHead := cur.Next
    // 很妙，利用指针，循环交替，把两个交叉链表分割开来了
    for cur != nil && cur.Next != nil {
        temp := cur.Next
        cur.Next = cur.Next.Next
        cur = temp
    }
    return cloneHead
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
  • 相关阅读:
    Linux 进阶 - 1
    【Linux】【驱动】设备树中设备节点的挂载
    C# String类的方法
    BUUCTF NewStarCTF 公开赛赛道Week4 Writeup
    【算法练习Day10】有效的括号&&删除字符串中的所有相邻重复项&&逆波兰表达式求值
    第 321 场力扣周赛
    Redis——》redis.conf
    JVM之运行时数据区 面试相关
    Go语言-九阴真经
    【STM32】学习笔记(OLED)
  • 原文地址：https://blog.csdn.net/EGXXM/article/details/127597132