链表基本算法浅析 GO语言版

算法

Posted by XuHAo on November 23, 2018

链表基本算法浅析 GO语言版

链表是我们常用的数据结构,关于链表的题目也常常在面试中遇到,出题的方式却不免大同小异,无外乎是解释链表结构、手写一个完整链表、链表相关的算法;进入精灵云的时候自己的操作系统的题做得不是很好,算法也没有ac,但是就因为手写了一个完整功能的双端循环链表结构拿下了实习,所以说链表基本功的扎实偶尔会在必要时帮自己一把。

这次写作目的是整理一下自己的链表基本算法,将在文中展现两个基本算法:单链表翻转和双链表交集。代码将用go进行演示,在后续中会更新一版python的代码演示。


单链表反转

  • 解释:

    单链表数据结构通常为多个单独节点node相链接,node中包含两个变量,一个记录node值,另一个记录该node节点下一个node的地址,无数个这样的结构就构成了常见的单链表。

  • 描述:

    单链表反转是指将一个由A->B->C的链表结构变为C->B->A的结构,操作的重点是在改变每个节点指向下一个节点的地址。

  • 思路:

    链表开始的位置一定都是由入口的head节点,然后按照顺序一次次操作运行到tail尾节点。我们可以想象若反转后的链表 A节点的下一个位置是什么,很明显A节点指向的下一个节点为null,那么我们再想反转后B节点的下一个节点是什么,没错是A节点。由B节点为例,B节点的下一个节点由C转向了A,这种一次次的反转就完成了对单链表的反转操作。

  • 代码展示:

    //构建一个node结构
    type node struct {
    	val  string
    	next *node
    }
      
    //main函数完成构建一个链表结构和调用验证链表的方法
    func main() {
    	//构建一个单链表
    	D := &node{val: "D", next: nil}
    	C := &node{val: "C", next: D}
    	B := &node{val: "B", next: C}
    	A := &node{val: "A", next: B}
    	root := &node{val: "root", next: A}
    	fmt.Println(root.AlonLink())
    }
      
    //链表反转的方法体
    func (this *node) AlonLink() *node {
    	if this.next == nil {
    		return this
    	}
    	H:=this        //设置h节点,h节点是保持节点变化时,作为反转的新next节点
    	P:=this.next   //操作节点
    	//指向一个空节点
    	P.next=nil   
    	if P.next!=nil {     //go 语言语法,相当于while循环 go也可以用for <条件代替>
    		Pr:=P.next       //临时节点,指向下一次工作的位置
    		P.next=H         //节点next指向变化
    		H=P              //H进一位
    		P=Pr             //工作区往后移动一次
    	}
    	//最后一个手动
    	P.next=H
    	return P
    }
    

双链表交集

  • 解释:

    双链表交集是指两个链表A、B,在非头节点的后续节点有交集,即两个链表之间有共享的部分,因为链表next指向结构决定了一旦两个链表相互有了交集,后面的都会是相同的结构。

  • 描述:(看图吧)

  • 思路:

    传统的验证回环后都是维护两个指针,一个快指针,一个慢指针,记得宇宙条问过不用快慢指针如何验证回环,这一次的代码会使用go程来对环进行验证,即开两个go程(可以理解为线程),A go程跑一圈,每次的步长为1,B go程跑两圈,每次的步长为2。到达后都会到起点,比较node之间的地址即可证明有环路。

  • 代码展示:

    func main() {
    	//构建一个双链表 但是有交集
    	F := &node{val: "F", next: nil}
    	E := &node{val: "E", next: F}
    	D := &node{val: "D", next: E}
    	C1 := &node{val: "C", next: D}
    	B1 := &node{val: "B", next: C1}
    	A1 := &node{val: "A", next: B1}
    	C2 := &node{val: "C2", next: D}
    	B2 := &node{val: "B2", next: C2}
    	A2 := &node{val: "A2", next: B2}
    	root1 := &node{val: "root", next: A1}
    	root2 := &node{val: "root", next: A2}
    	doubleLinkRing(root1, root2)
    }
      
    type node struct {
    	val  string
    	next *node
    }
      
    func doubleLinkRing(rootA, rootB *node) {
    	//将A表的尾 连入B链表的head,形成
    	fmt.Println("AAA")
    	tailA := rootA
    	//定位到尾部最后一位的node
    	for tailA.next != nil {
    		tailA = tailA.next
    	}
    	fmt.Println("AAA")
    	//统计B链表的长度
    	tailB := rootB
    	var lenB = 0
    	for tailB.next != nil {
    		tailB = tailB.next
    		lenB=lenB+1
    	}
      	
    	//链接A B链表 形成环!
    	tailA.next = rootB
    	chans := make(chan *node, 1)
      	
      	
    	//go 尝试开启双go程进行遍历
    	var wg sync.WaitGroup
    	wg.Add(1)
    	go func(chans chan *node, link *node) {
    		defer wg.Done()
    		runRing(1, lenB, chans, link)
    	}(chans, rootB)
      
    	wg.Add(1)
    	go func(len int, chans chan *node, link *node) {
    		defer wg.Done()
    		runRing(2, lenB, chans, link)
    	}(lenB, chans, rootB)
      
    	var listNode []*node
    	for i := 0; i < 2; i++ {
    		listNode = append(listNode, <-chans)
    	}
    	wg.Wait()
    	fmt.Printf("%d,%d",listNode[0],listNode[1])
    }
      
    //GO程 方法
    func runRing(step, len int, chans chan *node, link *node) {
    	for i := 0; i < len+1; i++ {
    		for j := 0; j < step; j++ {
    			link = link.next
    		}
    	}
    	chans <- link
    }