数据结构之链表相关算法剖析

miloyang
0 评论
/ /
942 阅读
/
8764 字
14 2023-09

在 链表基础 中，有讲解过单向、双向链表，忘记链表的增、删操作，可回头看看。
本文主要是针对链表的一些典型的算法做剖析。

经典一：单向链表翻转

链表为：1->2->3->null，需要把链表翻转为3->2->1->null。
先来个图：

danxianglianbiaofanz

代码如下： 

func ReverseNode(head *Node) *Node {
    var pre *Node // 为了保存当前node，因为当前node会被断掉，所以需要保留。
    var next *Node

    for head != nil {
        next = head.next
        head.next = pre
        pre = head
        head = next
    }
    return pre
}
  • 衍生：双向链表翻转
    其实，和单向一样，只是要注意把当前head节点的pre节点，需要指向上一个节点。
func ReverseDoublyNode(head *DoublyNode) *DoublyNode {
    var pre, next *DoublyNode
    for head != nil {
        next = head.next
        head.next = pre
        head.prev = next
        pre = head
        head = next
    }
    return pre
}

经典二：链表实现队列和栈

单链表Demo

  • 队列的实现：先进先出，每次添加从尾巴添加，每次出去从头部出去。
type LinkList struct {
    Head *Node
    Tail *Node
    Size int

    mu sync.Mutex
}

func (l *LinkList) Append(value int) {
    l.mu.Lock()
    defer l.mu.Unlock()

    newNode := &Node{
        value: value,
        next:  nil,
    }

    // 如果链头为空，说明还没有添加过node，新node既是头也是尾
    if l.Head == nil {
        l.Head = newNode
        l.Tail = newNode
    } else {
        l.Tail.next = newNode // 原来的尾部下一个指向新的，就形成了链条的关系
        l.Tail = newNode      // 每次新增的元素，向后添加，所以都是尾巴
    }
    l.Size++
}

func (l *LinkList) Poll() *Node {
    l.mu.Lock()
    defer l.mu.Unlock()

    var current *Node
    if l.Head == nil {
        return current
    }

    current = l.Head
    l.Head = l.Head.next
    l.Size--

    if l.Head == nil {
        l.Tail = nil // 如果头没了，尾巴也需要置空，否则会造成数据污染
    }
    return current
}

func (l *LinkList) Peek() *Node {
    var current *Node
    if l.Head == nil {
        return current
    }
    return l.Head
}
  • 栈的实现：每次都往头里面加，之前的头为当前节点的下一个。
type LinkStack struct {
    Head *Node
    Size int
    mu   sync.Mutex
}

func (l *LinkStack) Append(value int) {
    l.mu.Lock()
    defer l.mu.Unlock()

    newNode := &Node{
        value: value,
    }

    if l.Head == nil {
        newNode.next = nil
        l.Head = newNode
    } else {
        newNode.next = l.Head
        l.Head = newNode
    }
    l.Size++
}

func (l *LinkStack) Poll() *Node {
    l.mu.Lock()
    defer l.mu.Unlock()

    var current *Node
    if l.Head == nil {
        return current
    }
    
    current = l.Head
    l.Head = l.Head.next
    l.Size--
    return current
}

双链表实现队列和栈

案例：现实一个双链表，支持从头部和从尾部添加数据，从头部和从尾部弹出数据。 

type DoublyList struct {
    Head *DoublyNode
    Tail *DoublyNode

    mu sync.Mutex
}

// Append 在双向链表尾部插入节点
func (d *DoublyList) Append(value int) {
    d.mu.Lock()
    defer d.mu.Unlock()

    newNode := &DoublyNode{
        value: value,
        next:  nil, //  尾部插入，你就是尾部，则后继为nil
    }

    if d.Head == nil {
        d.Head = newNode
        d.Tail = newNode
    } else {
        d.Tail.next = newNode
        newNode.prev = d.Tail
        d.Tail = newNode
    }
}

// Prepend 在双向链表头部插入节点
func (d *DoublyList) Prepend(value int) {
    d.mu.Lock()
    d.mu.Unlock()

    newNode := &DoublyNode{
        value: value,
        prev:  nil, // 头部插入，说明你就是新头部，前驱当然为nil
    }

    if d.Head == nil {
        d.Head = newNode
        d.Tail = newNode
    } else {
        newNode.next = d.Head
        d.Head.prev = newNode
        d.Head = newNode
    }
}

func (d *DoublyList) PollHead() *DoublyNode {
    d.mu.Lock()
    defer d.mu.Unlock()

    var current *DoublyNode
    if d.Head == nil {
        return current
    }

    current = d.Head
    d.Head = current.next
    if d.Head == nil {
        d.Tail = nil
    } else {
        d.Head.prev = nil //头节点无前驱
    }
    return current
}

func (d *DoublyList) PollTail() *DoublyNode {
    d.mu.Lock()
    defer d.mu.Unlock()

    var current *DoublyNode
    if d.Tail == nil {
        return current
    }

    current = d.Tail
    d.Tail = current.prev

    if d.Tail == nil {
        d.Head = nil
    } else {
        d.Tail.next = nil //尾节点无后继
    }
    return current
}

经典三：实现链表根据k节点的组内逆序调整

题目：给定一个单链表的头部节点head，和一个证书k，实现k个节点的小组内部逆序，如果最后一组不够k就不调整，如k为2：    
调整前：1->2->3->4->5->nil
调整后:2->1->4->3->5->nil
相当于隔两个换一下位置

leetcode： k一个数组反转

逻辑图如下：

danlianbiaokf

代码：

func ReverseKGroup(head *Node, k int) *Node {
    // 单独处理第一次的查找，因为涉及到临界点
    start := head
    end := kGroupEnd(start, k)
    if end == nil {
        return head
    }
    head = end //无论怎样，头都是head了,固定住不变了
    reverse(start, end)
    lastEnd := start

    for lastEnd.next != nil {
        start = lastEnd.next
        end = kGroupEnd(start, k)
        if end == nil {
            return head
        }
        reverse(start, end)
        lastEnd.next = end
        lastEnd = start
    }
    return head
}

// 返回node节点下的k位置的节点
func kGroupEnd(node *Node, k int) *Node {
    for k--; k != 0 && node != nil; k-- {
        node = node.next
    }
    return node
}

// 根据开始的节点和结束的节点，进行翻转
func reverse(startNode *Node, endNode *Node) {
    end := endNode.next
    current := startNode
    var pre *Node
    var next *Node
    for current != end {
        next = current.next
        current.next = pre
        pre = current
        current = next
    }
    startNode.next = end
}

经典四 两个链表相加

给定两个链表的头结点head1，head2.
认为从左到右是某个数字从低位到高位，返回相加之后的链表，如：
h1   4->3->6
h2   2->5->3
返回 6->8->9
解释 634+352=986

h1  6->9->7
h2  8->5->9->5
返回 4->5->7->6
解释 796+5958=6754

思路：首先需要计算出h1和h2谁的链路短，链路短的先计算，再算链路长的，最后再算最后的进位。 如：

danlianbiaoadd

代码：

func LinkAdd(head1 *Node, head2 *Node) *Node {
    longNode, shortNode := compareLink(head1, head2)
    current := longNode
    carry := 0
    var longLastNode *Node // 为了最后一步把carry添加到后继节点，每次都需要记录长节点的最后节点

    for shortNode != nil {
        sub := shortNode.value + longNode.value + carry
        value := sub % 10
        carry = sub / 10
        longNode.value = value
        longLastNode = longNode
        longNode = longNode.next
        shortNode = shortNode.next

    }

    for longNode != nil {
        sub := longNode.value + carry
        value := sub % 10
        carry = sub / 10
        longNode.value = value
        longLastNode = longNode
        longNode = longNode.next

    }

    if carry != 0 {
        newNode := &Node{
            value: carry,
            next:  nil,
        }
        longLastNode.next = newNode
    }
    return current
}

// 根据传入的node，比较长度，然后返回长链表、短链表
func compareLink(n1 *Node, n2 *Node) (*Node, *Node) {
    n1Len := linkLen(n1)
    n2Len := linkLen(n2)
    if n1Len >= n2Len {
        return n1, n2
    }
    return n2, n1
}

func linkLen(n *Node) int {
    nodeLen := 0
    for n != nil {
        nodeLen++
        n = n.next
    }
    return nodeLen
}

经典五：两个有序链表的合并

给连个有序链表的节点:n1,n2，返回一个大链表，要求有序，如：
n1:6->9->17
n2:8->15->19->50
返回：6->8->9->15->17->19->50

思路：有了上道题的解法思路，这道题相对简单，也是算出长度，遍历短链表，对比两个链表的值，把短链表的值有序的插入到长链表中即可。

代码：

func linkMerge(n1, n2 *Node) *Node {
    longNode, shortNode := compareLink(n1, n2)
    current := longNode
    var longLast *Node

    for shortNode != nil {
        newNode := &Node{
            value: shortNode.value,
        }
        if longNode.value <= shortNode.value {
            newNode.next = longNode.next
            longNode.next = newNode
        } else {
            newNode.next = longNode
            if longLast != nil {
                longLast.next = newNode
            } else {
                current = newNode // 为空表示要添加在第一个节点上，此时longNode变成了newNode，current需要重新赋值
            }
        }
        longLast = longNode
        longNode = longNode.next
        shortNode = shortNode.next
    }

    return current
}
转载请注明来源： miloyang
本文链接： boxiaoyang.cn/article/125
<<数据结构之二叉树
数据结构之链表>>
人未眠
工作数十年
脚步未曾歇，学习未曾停
乍回首
路程虽丰富，知识未记录
   借此博客，与之共进步

分类