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

关注

发布于: 2020 年 11 月 09 日

﻿
以下完整的代码，及测试代码均可从这里获取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
	}
}
﻿