Go数据结构与力扣—链表

2021年4月9日 0 作者 y1nhui

前言

​ 因为想干纯后端,所以开始刷力扣巩固算法与数据结构,结果在写几天前的每日一题的时候发现自己对于链表的操作已经有些遗忘,以及对于链表的实现等也开始忘记。于是重新复习链表,并且写下这篇文章。

本文的主要内容为:链表的理论知识、代码实现与力扣部分链表相关题目及题解。(其实本来想写全部题目的,但是共有五十多道,一是写出来篇幅太长,而是要写完这五十多道,这篇文章就不知道要拖到多久之后才能完成了)

首先给出链表的定义:链表是数据元素的线性集合。它对对象实例的每一个元素用一个单元或节点描述。节点不鄙视数组成员,节点之间的地址也不是连续的。它们的位置是通过每一个节点中明确包含了一个节点地址信息的指针来确定的。

内容

基础知识

定义

单链表就是单向链表。每一个节点中有两个域。一个是链域负责储存指向下一链表地址的指针,一个是数据域,储存数据。

类型定义:

type chainNode struct {
    value int
    next *chainNode
}

头节点与头指针

我们定义了链表节点后,便可以实现一个单链表了。不过为了索引单链表,我们一般会提出一个东西:头节点。

链表第一个节点不一定是头节点,但是头节点一定是链表第一个节点。头节点代表的是放在链表第一个元素(存有数据)前的节点。它的值域一般是忽略的,它的存在意义是为了方便对链表的一些操作,并不是必须定义的。

而头指针则是指向链表第一个节点的指针,如果链表存在头节点,则指向头节点,若不存在头节点,就是指向链表第一个节点。

一般情况下头节点可以不存在,但头指针必须存在,因为我们需要依靠它来找到链表。

下面我们实现一个存在头节点的链表:

type chainNode struct {
    value int
    next *chainNode
}

func main(){

    chain := new(chainNode)


    node1 := &chainNode{5,nil}
    chain.next =node1


}

因为new关键字的作用是接受类型作为参数然后返回指向该类型的地址,所以这里chain便是头指针,它指向的chainNode便是头节点,二之后的node1才是真正的链表第一个元素。

单链表操作

声明:以下对节点的排序,我们默认头节点后的第一个节点为1.

链表的创建

无论是对链表进行什么操作,首先我们要创建一个链表,有了链表后才能进行操作。

而创建链表一般有两种方法,分别是头插法和尾插法

尾插法

尾插法,就是生成的每一个新节点都插入到当前链表的尾部。即将最后一个节点的链域指向它。

代码:

func createListTail(head *chainNode,n int) *chainNode{
    for node := head ; node != nil ; node = node.next {
        if node.next == nil {
            node.next = &chainNode{n,nil}
            break
        }
    }
    return head
}

这是我们只知道头指针的情况下的尾插法,当然如果我们知道尾指针的话,就可以快速很多了,所以一般情况下会设立尾指针来方便进行尾插法。

头插法

生成的每一个节点不再是插入到链表尾部,而是插入到头节点(我们默认存在头节点)之后。

这时的操作就是新节点的链域指向头节点的下一个节点,之后头节点的链域指向新节点。

代码:

func createListHead(head *chainNode,n int) *chainNode{
    node := &chainNode{n,head.next}
    head.next = node
    return head
}

因为不需要寻找尾指针,所以看上去更简单些

查找

其实写这个的时候挺纠结的,因为会发现各种资料中的查找有两个意思。

一个是知道序列取值,一个是知道值取地址(序列)。

不过它们的思路都是一样的,从头节点开始遍历,找出目标节点。

我以寻找第某个节点的值为例。

代码:

func get(head *chainNode,n int) (int,error) {
    i := 0
    for node := head ; node != nil ; node = node.next{
        if i==n {
            return node.value,nil
        }
    i++
    }

    return 0,errors.New("Can't Find")
}

在此基础上遍历表的所有元素,那么只需要将条件去除,每一个值都输出就可以了。

插入

若需要将某个节点插入到链表的第i位,那我们只需要将其的链域指向本来的第i位节点,然后将第i-1位的链域指向它即可。

代码:

func insert(head *chainNode,elem int,add int) (*chainNode,error) {
    i := 0
    for node:= head ; node != nil ; node = node.next {
        if i == add-1 {
            newNode := &chainNode{elem,node.next}
            node.next = newNode
            return head,nil
        }
        i++
    }

    return head,errors.New("overflow")
}

删除

若我们要删除第i个节点,只需将第i-1节点的链域指向第i+1,就可将第i节点从链表中删除。如果是c语言中我们还需要手动将被删除的节点的内存释放,不过考虑到go的内存释放机制,我们应该可以忽略这一步。

代码:

func del(head *chainNode,n int)  {
    i:=0
    for node:=head;node != nil ; node = node.next {
        if i == n-1 {
            node.next = node.next.next
            return
        }
        i++
    }
}

力扣题型

基础题

我对基础题的定义是只需要用到上面提到的基础操作,而不需要进行额外行为。

231290.二进制链表转正数 难度:简单

链表从头到位代表一个二进制整数,现在要求将其转为十进制并返回。

比较简单,从头开始取,每拿到一个就x2+后面的。

func getDecimalValue(head *ListNode) int {
    num := 0
    for node := head ; node != nil ; node=node.Next {
        num = num*2 +node.Val
    }
    return num
}

结果: 0ms 内存:2mb

剑指offer 22 链表中倒数第K个节点 难度:简单

题目的意思就是给一个数,比如3。则将从倒数第三个节点开始的链表返回。

那返回倒数第三个链表的指针不就好了。

那我们先写个简单的。首先遍历出链表长度n,那么倒数第k个节点就是正数第n-k+1的节点

func getKthFromEnd(head *ListNode, k int) *ListNode {
  n:=0
    cur := head
    for head.Next != nil {
        head = head.Next
        n++
    }

    for i:=1;i<=n-k+1;i++ {
        cur = cur.Next
    }
    return cur
}

结果: 4ms 内存:2.2mb

这一题还有一个有趣的解法,运行时间0ms,内存消耗只比上一种解法高几k,即是双指针。

双指针的解法想法就是,我们使用两个指针,快指针fast先走k步,然后两个指针一同运动。当fast走到尾的时候,slow正好走到了倒数第k个。

代码:

func getKthFromEnd(head *ListNode, k int) *ListNode {
    slow, fast := head, head
    for ;k > 0; k -- {
        fast = fast.Next
    }
    for fast != nil {
        slow, fast = slow.Next, fast.Next
    }
    return slow
}

876.链表的中间节点 难度:简单

题目要求简单,给出一个链表,需要返回中间节点。如果有两个中间节点就返回第二个.算是上一题的小变化

这种题目的第一个反应双指针

快指针一次走两步,慢指针一步,这样快指针走到底的时候慢指针走一半。

代码

func middleNode(head *ListNode) *ListNode {
    fast := head
    low := head
    for fast.Next != nil && fast.Next.Next != nil {
        fast=fast.Next.Next
        low = low.Next
    }
    if fast.Next != nil {
        return low.Next
    }else {
        return low
    }
}

21.合并两个有序链表 难度:简单

思路比较简单,生成一个假头后与两个链表中的值比较,谁小就连谁,之后与该链表下一个值及另一链表当前值比较。

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{0,nil}
    node := dummy
    for l1 !=nil && l2!=nil {
        if l1.Val < l2.Val {
            node.Next = l1
            node = node.Next
            l1 = l1.Next
        }else {
            node.Next = l2
            node = node.Next
            l2 = l2.Next
        }
    }
    switch {
    case l1 != nil:
            node.Next = l1
    case l2 != nil:
            node.Next = l2  
    }

    return dummy.Next
}

时间复杂度:O(n^2) 内存消耗:2.5mb

双100%

进阶题

这类题型的定义是除了上述基础操作外,需要进行一些对链表链域变动的行为。

7.删除链表中的节点 难度:简单

这一题比较简单,它的要求就是只传入一个节点,然后我们要删除这个节点。

这个就比较简单了,我们只需要这个节点成为下一个节点就好了。

func deleteNode(node *ListNode) {
   *node = *node.Next 
}

这里有个点,就是我们写的是*node 而不是 node

因为我们这里并没有return,直接写node的话作用域只是函数内,因此需要写*node来对真实的指针进行更改。

82.删除链表中的排序元素 难度:中等

题目比较简单,因为是排序链表,一次遍历,将node与node.next对比就好了。

不过力扣不讲武德,头节点的值居然是需要考虑的有效值

所以要考虑头节点情况,就新加个节点当头节点。

然后一个指针cur开始循环,它是安全的,它要比的是next与next.next的值,如果相等就删除。

同时为了比较方便(直接比较跳过容易把奇数次重复给留个尾巴),我们写一个标志位储存val,用来对比。

代码:

func deleteDuplicates(head *ListNode) *ListNode {
    newHead := &ListNode{0,head}
    cur := newHead
    for cur.Next != nil &&  cur.Next.Next != nil {
        if cur.Next.Val == cur.Next.Next.Val{
            v := cur.Next.Val
            for cur.Next != nil && cur.Next.Val == v {
                cur.Next = cur.Next.Next
            }
        }else {
            cur = cur.Next
        }
    }

    return newHead.Next
}

19.删除链表的倒数第N个节点 难度:中等

这就是倒数第k个节点与删除节点的组合

快慢指针解决

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummpy := &ListNode{0,head}
    fast,slow := dummpy,dummpy
    for n>=0 {
        fast = fast.Next
        n-- 
    }
    for fast != nil {
        slow,fast = slow.Next,fast.Next
    }
    if slow.Next.Next!=nil{
        slow.Next = slow.Next.Next
    }else{
        slow.Next = nil
    }

    return dummpy.Next
}

206.反转链表 && 剑指Offer 24 难度:简单

加上头指针一共用了三个指针的遍历法

一个pre,记录.next 一个cur记录上一节点。

ctQsJg.png

如图,这是一开始的样子

然后,将head.next指向cur,cur=head,head=pre,pre=head.next

ctQ6zj.png

就变成了这样,由此往复,便可将链表完全倒转过来

代码:

func reverseList(head *ListNode) *ListNode {
    var cur *ListNode
    for head != nil {
        pre := head.Next
        head.Next = cur
        cur = head
        head = pre
    }
    return cur
}

面试题02.07 链表相交 难度:简单

检查两个链表中是否有节点相交

一开始想的是遍历来对比,后来发现还是可以双指针解法

如果两个链表相交的话,那么当两个指针在走完自己链表后走对面链表的话,必定会相交。

a \
o – c

b /

这样看,假设两指针分别从a、b到c,之后再从b、a到c

那么它们的移动距离分别是 ao+ob+bo=bo+oc+ao,再加上两指针速度相同,所以他们必定相遇

那么当他们相遇,且有值当时候,就说明两链表相交

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    p1, p2 := headA, headB
    for p1 != p2 {
        if p1 == nil {
            p1 = headB
        } else {
            p1 = p1.Next
        }
        if p2 == nil {
            p2 = headA
        } else {
            p2 = p2.Next
        }
    }
    return p1
}

234.回文链表 难度:简单

​ 快慢指针找重点断开后做链表反转然后对比

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil{
        return true
    }   
    slow,fast := head,head
    var pre *ListNode

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

    var dummy *ListNode
    for slow != nil {
        fast = slow.Next
        slow.Next = dummy
        dummy = slow
        slow = fast
    }

    for dummy!=nil && head != nil {
        if dummy.Val != head.Val{
            return false
        }
        head = head.Next
        dummy = dummy.Next
    }

    return true
}

剑指offer 35.复杂链表的复制 难度:中等

这一题的解法可以这样。

我们先将之当成单链表,复制节点的next与val,然后再复制指针。

但是直接复制指针的话,指向地址不是新节点的地址。 我们可以将新节点直接插入每一个旧节点之后,然后指针=旧指针指向节点的next

之后我们再将新节点都分离出来,新成新链表输出。(记得将原链表拼回去,不然会报错Next pointer of node with label 13 from the original list was modified.)

代码:

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil 
    }
    node := head
    for node!=nil {
        newNode := &Node{
            node.Val,
            node.Next,
            nil,
        }
        node.Next = newNode
        node = newNode.Next
    }

    node = head 
    for node!=nil {
        if node.Random != nil {
            node.Next.Random = node.Random.Next
        }
        node = node.Next.Next
    }

    newHead := head.Next
    oldNode := head
    node = newHead

    for node.Next != nil {
        oldNode.Next = oldNode.Next.Next
        node.Next = node.Next.Next
        oldNode = oldNode.Next
        node = node.Next
    }
    oldNode.Next = nil
    return newHead
}

142.环形链表2 难度:中等

快慢指针解法。不过需要注意一个问题,那就是我们快慢指针会相遇,但不一定会在第一个节点相遇。

func detectCycle(head *ListNode) *ListNode {
    slow,fast := head,head
    for fast != nil&&fast.Next != nil {   //考虑有指向nil这种阴间行为,记得.next!=nil
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast{
            node := head
            for node != slow {
                node = node.Next
                slow = slow.Next
            }
            return node
        }
    }

    return nil

148.排序链表 难度:中等

想法1 直接取值入数组排序然后重写

func sortList(head *ListNode) *ListNode {
    l1 := []int{}
    for node:=head;node != nil ;node = node.Next{
        l1 = append(l1,node.Val)
    }
    sort.Ints(l1)
    i:=0
    for node:=head;node !=nil;node=node.Next{
        node.Val = l1[i]
        i++
    }
    return head
}

我本来以为超时的,没想到通过了

常规解法是归并排序

我们先将链表多次等分,得出单个链表。

然后结合之前的合并有序链表的想法进行两两合并,得出结果

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { // 递归的出口,不用排序 直接返回
        return head
    }
    slow,fast := head,head
    var pre *ListNode
    for fast != nil && fast.Next != nil {
        pre = slow
        slow = slow.Next
        fast = fast.Next.Next
    }
    pre.Next = nil

    l1 := sortList(head)
    l2 := sortList(slow)

    return mergeList(l1,l2)
}


func mergeList(l1,l2 *ListNode) *ListNode {
    dummy := &ListNode{0,nil}
    node := dummy
    for l1!=nil && l2!=nil {
        if l1.Val < l2.Val {
            node.Next = l1
            l1 = l1.Next
        }else {
            node.Next = l2
            l2 = l2.Next
        }
        node = node.Next
    }
    switch  {
    case l1 != nil:
        node.Next = l1
    case l2 != nil:
        node.Next = l2
    }

    return dummy.Next
}