IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
    • 登录 注册

    『代码随想录』链表（Linked List）

    NX の 博客发表于 2023-10-27 03:42:16
    love 0

    DAY 3

    本篇部分题目在 『算法拾遗』链表（Linked List） 中已经做过

    203.移除链表元素

    还有一个递归版，但是那个空间复杂度是 O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    func removeElements(head *ListNode, val int) *ListNode {
        dummy := &ListNode{Next: head}
        curr := dummy
        for curr.Next != nil {
            if curr.Next.Val == val {
                curr.Next = curr.Next.Next
            } else {
                curr = curr.Next
            }
        }

        return dummy.Next
    }

    707.设计链表

    分别写了单向链表和双向链表两个版本

    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
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    type MyLinkedList struct {
        head *LinkNode
        size int
    }

    type LinkNode struct {
        val  int
        next *LinkNode
    }

    func Constructor() MyLinkedList {
        dummyHead := &LinkNode{}
        return MyLinkedList{
            head: dummyHead,
            size: 0,
        }
    }

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

    func (this *MyLinkedList) AddAtHead(val int) {
        newNode := &LinkNode{val: val}
        newNode.next = this.head.next
        this.head.next = newNode
        this.size++
    }
    func (this *MyLinkedList) AddAtTail(val int) {
        newNode := &LinkNode{val: val}
        cur := this.head
        for cur.next != nil {
            cur = cur.next
        }
        cur.next = newNode
        this.size++
    }

    func (this *MyLinkedList) AddAtIndex(index int, val int) {
        if index < 0 || index > this.size {
            return
        }
        if index == this.size {
            this.AddAtTail(val)
            return
        }
        cur := this.head
        for i := 0; i < index; i++ {
            cur = cur.next
        }
        newNode := &LinkNode{val: val}
        newNode.next = cur.next
        cur.next = newNode
        this.size++
    }

    func (this *MyLinkedList) DeleteAtIndex(index int) {
        if index < 0 || index >= this.size {
            return
        }
        cur := this.head
        for i := 0; i < index; i++ {
            cur = cur.next
        }
        cur.next = cur.next.next
        this.size--
    }
    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
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    type MyLinkedList struct {
        size int
        head *Node
        tail *Node
    }

    type Node struct {
        val        int
        next, prev *Node
    }

    func Constructor() MyLinkedList {
        dummy := &Node{}
        dummy.next = dummy
        dummy.prev = dummy

        return MyLinkedList{
            size: 0,
            head: dummy,
            tail: dummy,
        }
    }

    func (this *MyLinkedList) Get(index int) int {
        if index < 0 || index >= this.size {
            return -1
        }
        curr := this.head.next
        for i := 0; i < index; i++ {
            curr = curr.next
        }
        return curr.val
    }

    func (this *MyLinkedList) AddAtHead(val int) {
        newNode := &Node{
            val:  val,
            next: this.head.next,
            prev: this.head,
        }
        this.head.next.prev = newNode
        this.head.next = newNode
        this.size++
    }

    func (this *MyLinkedList) AddAtTail(val int) {
        newNode := &Node{
            val:  val,
            next: this.tail,
            prev: this.tail.prev,
        }
        this.tail.prev.next = newNode
        this.tail.prev = newNode
        this.size++
    }

    func (this *MyLinkedList) AddAtIndex(index int, val int) {
        if index < 0 || index > this.size {
            return
        }
        curr := this.head.next
        for index != 0 {
            curr = curr.next
            index--
        }
        newNode := &Node{
            val:  val,
            prev: curr.prev,
            next: curr,
        }
        curr.prev.next = newNode
        curr.prev = newNode
        this.size++
    }

    func (this *MyLinkedList) DeleteAtIndex(index int) {
        if index < 0 || index >= this.size {
            return
        }
        curr := this.head.next
        for index != 0 {
            curr = curr.next
            index--
        }
        curr.next.prev = curr.prev
        curr.prev.next = curr.next
        this.size--
    }

    206.反转链表

    经典反转链表，操作过程如下

    1. 初始化当前节点为头节点
    2. 暂存下一个节点
    3. 将当前节点指向前一个节点
    4. 前驱节点后移
    5. 当前节点后移
    6. 重复 1-4，只到当前节点为 NULL ，输出前驱结点为新的头结点
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    func reverseList(head *ListNode) *ListNode {
    // 定义前驱节点、当前节点、后继节点
    var prev *ListNode = nil
    var next *ListNode = nil
    var curr *ListNode = head

    // 遍历链表
    for curr != nil {
    // 保存下一个节点
    next = curr.Next
    // 当前节点指向前驱节点
    curr.Next = prev
    // 前驱节点后移
    prev = curr
    // 当前节点后移
    curr = next
    }

    // 返回前驱节点
    return prev
    }

    我一开始也不是很懂，所以我画了个图一步一步来，图画出来我就懂了

    image-20230601下午103709377

    类似地，还有一个递归的写法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    func reverseList(head *ListNode) *ListNode {
    // 如果链表为空或者只有一个节点，直接返回原链表
    if head == nil || head.Next == nil {
    return head
    }
    // 递归反转除头节点外的子链表
    p := reverseList(head.Next)
    // 将当前节点的下一个节点指向当前节点，实现反转
    head.Next.Next = head
    // 将当前节点的下一个节点置空，断开原链表中的连接
    head.Next = nil
    // 返回反转后的链表的头节点
    return p
    }

    DAY 4

    本篇部分题目在 『算法拾遗』链表（Linked List） 中已经做过

    24.两两交换链表中的节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    func swapPairs(head *ListNode) *ListNode {
        dummy:=&ListNode{
            Next: head,
        }

        curr := dummy

        for curr!=nil && curr.Next!=nil && curr.Next.Next != nil{
            first:=curr.Next
            second:=curr.Next.Next

            first.Next=second.Next
            second.Next=first
            curr.Next=second

            curr=curr.Next.Next
        }

        return dummy.Next
    }

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

    经典快慢指针

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    func removeNthFromEnd(head *ListNode, n int) *ListNode {
        dummy := &ListNode{
            Next: head,
        }
        fast, slow := dummy, dummy

        for i := 1; i < n; i++ {
            fast = fast.Next
        }

        for fast.Next.Next != nil {
            fast = fast.Next
            slow = slow.Next
        }

        slow.Next = slow.Next.Next

        return dummy.Next
    }

    面试题02.07.链表相交

    双指针，先对齐再往后走

    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
    func getIntersectionNode(headA, headB *ListNode) *ListNode {
        lenA, lenB := 0, 0

        for curr := headA; curr != nil; curr = curr.Next {
            lenA++
        }
        for curr := headB; curr != nil; curr = curr.Next {
            lenB++
        }

        if lenA < lenB {
            headA, headB = headB, headA
            lenA, lenB = lenB, lenA
        }

        diff := lenA - lenB

        a, b := headA, headB
        for i := 0; i < diff; i++ {
            a = a.Next
        }

        for a != nil && b != nil {
            if a == b {
                return a
            }
            a = a.Next
            b = b.Next
        }
        return nil
    }

    142.环形链表 II

    快慢指针找环，然后让其中一个回到原点，再同步前进

    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
    func detectCycle(head *ListNode) *ListNode {
        dummy := &ListNode{
            Next: head,
        }

        fast, slow := dummy, dummy

        for fast != nil && fast.Next != nil {
            fast = fast.Next.Next
            slow = slow.Next

            if fast == slow {
                break
            }
        }

        if fast == nil || fast.Next == nil {
            return nil
        }

        fast = dummy

        for fast != slow {
            fast = fast.Next
            slow = slow.Next
        }

        return fast

    }

    DAY 5

    周日休息



沪ICP备19023445号-2号
友情链接