0、go语言 自定义 链表节点
type Node struct {
Data int
Next *Node
}
type DoubleNode struct {
Data int
Next *DoubleNode
Pre *DoubleNode
}
1、单链表反转
1）遍历到当前节点cur，先获取next节点，将当前节点的next指向前一个节点pre。更新当前节点为next,所以需要一个pre初始化为nil的变量。
2）终止条件就是cur节点为nil
错误点：未更新pre。。
func ReverseLinkedList(head *Node) *Node{
var pre *Node
var next *Node
for head != nil {
next = head.Next
head.Next = pre
pre = head
head = next
}
return pre
}
这个打败是太假了。有的打败0%。
2、双链表反转
- 先获取next节点。把当前节点cur的next指向pre节点，pre节点的pre指向cur节点。
- 更新 pre、cur节点
- 终止条件，cur = nil
func ReverseDoubleLinkedList(head *DoubleNode) *DoubleNode{
var pre *DoubleNode
var next *DoubleNode
for head != nil {
next = head.Next
head.Next = pre
pre.Pre = head
pre = head
head = next
}
return pre
}
不出意外的话，出意外了
空指针，因为用到pre.pre了。必须保证pre不为nil,简单点，从第二个节点开始遍历。pre初始化为第一个节点。
func ReverseDoubleLinkedList(head *DoubleNode) *DoubleNode {
if head == nil {
return nil
}
var pre *DoubleNode
pre = head
head = head.Next
var next *DoubleNode
for head != nil {
next = head.Next
head.Next = pre
pre.Pre = head
pre = head
head = next
}
return pre
}
再跑：死循环了。。很明显还需要
打印返回的新的首节点,发现Next和Pre是同一个对象。后置处理：应该要把pre.pre置空。新的首节点的Pre肯定是空的，这里不是循环双向链表。
func ReverseDoubleLinkedList(head *DoubleNode) *DoubleNode {
if head == nil {
return nil
}
var pre *DoubleNode
pre = head
head = head.Next
pre.Next = nil //需要将末尾节点的Next节点置空。不然死循环。
var next *DoubleNode
for head != nil {
next = head.Next
head.Next = pre
pre.Pre = head
pre = head
head = next
}
pre.Pre = nil
return pre
}
错误点：新的尾节点的next置空。新的首节点的pre置空。
-上面是更新当前节点的Next和Pre节点Pre.要是换一种更新，遍历到当前节点，只更新当前节点的Next和Pre.就简单了。。
func ReverseDoubleLinkedList_02(head *DoubleNode) *DoubleNode {
if head == nil {
return nil
}
var pre *DoubleNode
var next *DoubleNode
for head != nil {
next = head.Next
head.Next = pre
head.Pre = next
pre = head
head = next
}
return pre
}
这种基本题，不训练还是不行。唉。太笨了。
3、打印两个有序链表的公共部分
- 谁小谁右移
- 一样打印，都右移
- 终止条件：其中任何一个遍历完了。
func PrintCommonLinkedList(head1 *Node, head2 *Node) {
for head1 != nil && head2 != nil {
if head1.Data == head2.Data {
fmt.Print(head1.Data)
head1 = head1.Next
head2 = head2.Next
} else if head1.Data > head2.Data {
head2 = head2.Next
} else {
head1 = head1.Next
}
}
}
- 技巧1：额外哈希表记录
- 技巧2：快慢指针，双指针
- 技巧3：增加一个首节点好处理数据。
4、判断一个链表是否为回文结构
方法1：使用额外空间，
- 使用一个栈，把链表先入栈，然后出栈和链表一一对比。如果有不一样的：false.如果遍历完都一样，就true
func IsPalindromLinkedList_01(head *Node) bool {
arr := make([]int, 10)
i := 0
cur := head
for cur != nil {
arr[i] = cur.Data
i++
cur = cur.Next
}
i--
cur = head
for i >= 0 && cur != nil {
if arr[i] != cur.Data {
return false
}
i--
cur = cur.Next
}
return true
}
方法二，快慢指针。节省一半空间
- 慢指针slow一次走一步,快指针fast一次走俩步，如果其中一个next指针为空，停止，慢指针走的数都进栈。
- 如果是奇数个，那么慢指针正好在最中间。如果是偶数个，那么慢指针在左半边最后一个。
- 慢指针的下一个数依次和栈里的数一一比较。
错误示例：
func IsPalindromLinkedList_02(head *Node) bool {
arr := make([]int, 10)
i := 0
slow := head
fast := head
for slow.Next != nil && fast.Next.Next != nil {
arr[i] = slow.Data
i++
slow = slow.Next
fast = fast.Next.Next
}
i--
right_first := slow.Next
for i >= 0 {
if arr[i] != right_first.Data {
return false
}
i--
right_first = right_first.Next
}
return true
}
- 思路2： right表示右边第一个元素。 cur每次都俩步，right每次走一步。cur.next 为空或者cur.next.next为空，right已经到了最右边第一个。这里必须先判断cur.next不为空，再判断cur.next.next。循环完成之后。将right和right后面的元素全部入栈，然后依次出栈和head开始比较。
func IsPalindromLinkedList_03(head *Node) bool {
if head == nil || head.Next == nil {
return false
}
cur := head
right := head.Next
// right每次向右移动一个，cur每次向右移动俩个
for cur.Next != nil && cur.Next.Next != nil {
right = right.Next //能进来说明right 不为空
cur = cur.Next.Next // 更新cur. cur为空了。right走到右边第一个
}
// 把right后边的元素都入栈
arr := make([]int, 10)
i := 0
for right != nil {
arr[i] = right.Data
right = right.Next
i++
}
i--
// 出栈和头节点开始依次对比，直到栈中无元素。
for i >= 0 {
if arr[i] != head.Data {
return false
}
i--
head = head.Next
}
return true
}
方法3：额外空间为0.
遍历的时候，顺便把左或右半部分的链表翻转了。
然后开始从中间像俩边比较
还要恢复。。
func IsPalindromLinkedList_04(head *Node) bool {
if head == nil || head.Next == nil {
return true
}
// right := head.Next //right 从 next出发。不好获取左边最后一个元素。
right := head //从 head出发，遍历完之后。right是左边最后一个元素
cur := head
for cur.Next != nil && cur.Next.Next != nil {
right = right.Next
cur = cur.Next.Next
}
left_last := right //保存左边最后一个元素，也有可能是中间值
right_first := right.Next // 右边第一个值
left_last.Next = nil // 断开
right_last := ReverseLinkedList(right_first) //将右半部分翻转
// 比较, 如果其中一个到头了。就结束
res := true
right_node := right_last
left_node := head
for right_node != nil && left_node != nil {
if right_node.Data != left_node.Data {
res = false
}
right_node = right_node.Next
left_node = left_node.Next
}
// 右半部分再翻转回来。
right_first = ReverseLinkedList(right_last)
left_last.Next = right_first // 左右连接
return res
}