链表操作练习题

加强巩固对链表的理解，以及一些操作思路，从网络搜集了一些链表的操作习题，使用Go进行了一些实现。

先初始化一个单向链表：

package linked

import "fmt"

// 定义节点
type Element struct {
   Value interface{}
   Next *Element
}
// 创建一个单向链表
func New(values ...interface{}) (head *Element) {
   var prev = &Element{}
   for k,v := range values{
      e := &Element{v, nil}
      if k == 0 {
         head = e
         prev = head
         continue
      }
      prev.Next = e
      prev = e
   }
   return
}

// 打印单向链表
func (h *Element)Print() {
   next := h
   for i:=0; next != nil; i++ {
      fmt.Printf("第%d元素值：%v 内存地址：%p \n",i, next, next)
      next = next.Next
   }
}

//根据元素位置查找
func (h *Element)Find(pos int) *Element {
   next := h
   for i:=0; next != nil; i++ {
      if i == pos { break }
      next = next.Next
   }
   return next
}

package main

import (
   "learn/linked"
)

func main() {
   head := linked.New(11,2,15,8,9,29,32,43)
   head.Print()
}

输出结果：
第0元素值：&{11 0xc0000a6040} 内存地址：0xc0000a6020 
第1元素值：&{2 0xc0000a6060} 内存地址：0xc0000a6040 
第2元素值：&{15 0xc0000a6080} 内存地址：0xc0000a6060 
第3元素值：&{8 0xc0000a60a0} 内存地址：0xc0000a6080 
第4元素值：&{9 0xc0000a60c0} 内存地址：0xc0000a60a0 
第5元素值：&{29 0xc0000a60e0} 内存地址：0xc0000a60c0 
第6元素值：&{32 0xc0000a6100} 内存地址：0xc0000a60e0 
第7元素值：&{43 <nil>} 内存地址：0xc0000a6100

下面的操作都基于初始化的单向链表进行操作

1、删除指定的链表节点

分析：主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。

package main

import (
   "learn/linked"
)

func main() {
   head := linked.New(11,2,15,8,9,29,32,43)
   head.Print()
   // 查找待删除的节点
   e := head.Find(7)
   deleteElement(head, e)
   head.Print()
}

func deleteElement(head, e *linked.Element)  {
   // 删除末尾节点
   if e.Next == nil {
      current := head
      for current != nil {
         if current.Next == e {
            current.Next = nil
            break
         }
         current = current.Next
      }
      return
   }
   // 非末尾节点
   e.Value = e.Next.Value
   e.Next = e.Next.Next
   return
}

第0元素值：&{11 0xc00011c040} 内存地址：0xc00011c020 
第1元素值：&{2 0xc00011c060} 内存地址：0xc00011c040 
第2元素值：&{15 0xc00011c080} 内存地址：0xc00011c060 
第3元素值：&{8 0xc00011c0a0} 内存地址：0xc00011c080 
第4元素值：&{9 0xc00011c0c0} 内存地址：0xc00011c0a0 
第5元素值：&{29 0xc00011c0e0} 内存地址：0xc00011c0c0 
第6元素值：&{32 0xc00011c100} 内存地址：0xc00011c0e0 
第7元素值：&{43 <nil>} 内存地址：0xc00011c100 
第0元素值：&{11 0xc00011c040} 内存地址：0xc00011c020 
第1元素值：&{2 0xc00011c060} 内存地址：0xc00011c040 
第2元素值：&{15 0xc00011c080} 内存地址：0xc00011c060 
第3元素值：&{8 0xc00011c0a0} 内存地址：0xc00011c080 
第4元素值：&{9 0xc00011c0c0} 内存地址：0xc00011c0a0 
第5元素值：&{29 0xc00011c0e0} 内存地址：0xc00011c0c0 
第6元素值：&{32 <nil>} 内存地址：0xc00011c0e0

2、输出一个单链表的逆序反转后的链表

解法一：分析：非递归的算法很简单，用三个临时指针 prev、cur、next 在链表上循环一遍即可。递归算法是先逆转下一个节点，再逆转当前节点。

package main

import (
   "learn/linked"
)

func main() {
   head := linked.New(11,2,15,8,9,29,32,43)
   head.Print()
   // 输出一个单链表的逆序反转后的链表
   head = reverseByLoop(head)
   head.Print()
}

func reverseByLoop(head *linked.Element) *linked.Element {
   if head.Next == nil {
      return head
   }
   var prev, current, next *linked.Element = nil, head, nil
   for current != nil {
      next = current.Next
      current.Next = prev
      prev = current
      current = next
   }
   return prev
}

输出结果：
第0元素值：&{11 0xc00011c040} 内存地址：0xc00011c020 
第1元素值：&{2 0xc00011c060} 内存地址：0xc00011c040 
第2元素值：&{15 0xc00011c080} 内存地址：0xc00011c060 
第3元素值：&{8 0xc00011c0a0} 内存地址：0xc00011c080 
第4元素值：&{9 0xc00011c0c0} 内存地址：0xc00011c0a0 
第5元素值：&{29 0xc00011c0e0} 内存地址：0xc00011c0c0 
第6元素值：&{32 0xc00011c100} 内存地址：0xc00011c0e0 
第7元素值：&{43 <nil>} 内存地址：0xc00011c100 
第0元素值：&{43 0xc00011c0e0} 内存地址：0xc00011c100 
第1元素值：&{32 0xc00011c0c0} 内存地址：0xc00011c0e0 
第2元素值：&{29 0xc00011c0a0} 内存地址：0xc00011c0c0 
第3元素值：&{9 0xc00011c080} 内存地址：0xc00011c0a0 
第4元素值：&{8 0xc00011c060} 内存地址：0xc00011c080 
第5元素值：&{15 0xc00011c040} 内存地址：0xc00011c060 
第6元素值：&{2 0xc00011c020} 内存地址：0xc00011c040 
第7元素值：&{11 <nil>} 内存地址：0xc00011c020

 解法二：递归至链表的最后一个节点开始，从后往前更改指针

package main

import (
   "learn/linked"
)

func main() {
   head := linked.New(11,2,15,8,9,29,32,43)
   head.Print()
   // 输出一个单链表的逆序反转后的链表
   head = reverseByRecursion(head)
   head.Print()
}

func reverseByRecursion(head *linked.Element) *linked.Element {
   // 递归结束条件，至链表末尾
   if head.Next == nil {
      return head
   }
   newHead := reverseByRecursion(head.Next)
   head.Next.Next = head
   head.Next = nil
   return newHead
}

 3、删除单链表倒数第 n 个节点

分析：使用快慢指针；看到题目时的第一想法是先遍历一次计算出单链表的长度 length，然后在遍历第二次删除第 length – n + 1 个节点，但是这需要遍历两次。正常的删除第 n 个节点只需要遍历一次就可以，如何只遍历一次找到倒数第 n 个节点呢？可以设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，p2 移动到第 n 个节点，然后 p1 和 p2 同时向后移动，当 p2 移动到末尾时，p1 刚好指向倒数第 n 个节点。因为最后要删除倒数第 n 个节点，所以可以找到倒数第 n + 1 个节点，方便删除节点。