数据结构与算法系列之链表操作全集(三)(GO)

微信扫一扫,分享到朋友圈

数据结构与算法系列之链表操作全集(三)(GO)

以下完整的代码,及测试代码均可从这里获取 github

删除单向链表倒数第n个结点

方法一:快慢指针法

思路

删除倒数第N个结点,假设反过来看,要删除第N个节点。那么,一个指向头结点(头结点中也是一个数据结点)的指针向前移动N-1个结点后,指向的就是第N个结点

现在再看删除倒数第N个结点,假设此时有两个指针(快指针fastPtr、慢指针lowPtr)均指向头结点,快指针fastPtr向后遍历N-1个结点之后,慢指针和快指针开始一起向后遍历,当快指针到达最后一个结点的时候,慢指针指向的位置,就是倒数第N个结点的位置

代码实现

func (list *List) DelLastNNode1(lastN int) {
if lastN > list.Length() || lastN <= 0 {
fmt.Println("输入的待删结点位置不合法")
return
}
//删除尾结点
if lastN == 1 {
list.RemoveLastNode()
return
}
//删除头结点
if lastN == list.Length() {
//删除链表头结点
list.headNode = list.headNode.Next
return
}
lowNode := list.headNode
fastNode := list.headNode
prevNode := list.headNode
fastStep := lastN-1
for fastNode.Next != nil {
if fastStep > 0 {
fastNode = fastNode.Next
fastStep--
continue
}
fastNode = fastNode.Next
prevNode = lowNode
lowNode = lowNode.Next
}
prevNode.Next = lowNode.Next
}

方法二:结点位置和结点数量的关系法

思路

不知道怎么删除倒数第N个结点,想办法知道它是第几个不就行了。所以,关键是通过链表长度以及N来找到倒数第N个结点是正数第几个节点,通过观察可以得到,倒数第N个结点就是正数第length-N+1个结点,length为链表长度

代码实现

func (list *List) DelLastNNode2(lastN int) {
if lastN > list.Length() || lastN <= 0{
fmt.Println("输入的待删结点位置不合法")
return
}
length := list.Length()
position := length-lastN+1
if position == 1 {
//删除链表头结点
list.headNode = list.headNode.Next
} else if position == length {
//删除链表的尾结点
list.RemoveLastNode()
} else {
//删除链表中指定位置的结点
list.RemovePosition(position)
}
}

说明:删除单链表头结点、尾结点、指定位置的节点实现,可以参考我的 这一篇文章 ,或者这里

https://github.com/Rain-Life/data-struct-by-go

两个有序的单链表合并

该题也是LeetCode上第21题

方法一:常规方法

思路

常规思路就是,创建一个新的链表,然后遍历待合并的两个链表,比较遍历到的两个结点值的大小,假设要合并之后的链表按照从小到大排序,值小的那个结点插入到新的链表中,并将值小的那个结点向后遍历一位,值大的那个结点保持不变,然后继续比较,重复上边步骤,如图(注意:为了展示过程,下图中未考虑链表是否为空的情况)

代码实现

func (list *List) MergeLinkedList(list1 List, list2 List) {
if list1.HeadNode == nil && list2.HeadNode == nil {
fmt.Println("两个链表均为空")
return
} else if list1.HeadNode == nil {
list.HeadNode = list2.HeadNode
return
} else if list2.HeadNode == nil {
list.HeadNode = list1.HeadNode
return
}
curr1 := list1.HeadNode
curr2 := list2.HeadNode
if curr1.Data.(int) < curr2.Data.(int) {
list.HeadNode = curr1
curr1 = curr1.Next
} else {
list.HeadNode = curr2
curr2 = curr2.Next
}
newHead := list.HeadNode
currNew := newHead
for curr1 != nil && curr2 != nil {
if curr1.Data.(int) < curr2.Data.(int) {
currNew.Next = curr1
curr1 = curr1.Next
} else {
currNew.Next = curr2
curr2 = curr2.Next
}
currNew = currNew.Next
}
if curr1 == nil {
currNew.Next = curr2
}
if curr2 == nil {
currNew.Next = curr1
}
}

方法二:递归

思路

将上边的常规解法用递归来实现,主要是递归的终止条件

代码实现

func RecursionMergeList(head1 *Node, head2 *Node) *Node {
newNode := &Node{}
if head1 == nil {
return head2
} else if head2 == nil {
return head1
} else {
if head1.Data.(int) < head2.Data.(int) {
newNode = head1
newNode.Next = RecursionMergeList(head1.Next, head2)
} else {
newNode = head2
newNode.Next = RecursionMergeList(head1, head2.Next)
}
return newNode
}
}

有疑问加站长微信联系(非本文作者)

微信扫一扫,分享到朋友圈

数据结构与算法系列之链表操作全集(三)(GO)

彩虹排序 | 荷兰旗问题

上一篇

多款3000元内5G机型上市 市场竞争趋于白热化

下一篇

你也可能喜欢

数据结构与算法系列之链表操作全集(三)(GO)

长按储存图像,分享给朋友