常规链表题相对简单
引用一位大佬的名言:
链表的题通常需要注意:
1. 舍得用变量,千万别想着节省变量,否则容易被逻辑绕晕。
2. head 有可能需要改动时,先增加一个假head,返回的时候直接取假head.next,这样就不需要为修改 head 增加一大堆逻辑了。
3. 迭代法很简单,但是容易绕晕,想不明白的时候,就画图。
4. 哑节点很重要,能够提供很多帮助。
237. 删除给定节点
如何让自己在世界上消失,但又不死? —— 将自己完全变成另一个人,再杀了那个人就行了。
func deleteNode(node *ListNode) {
//写的时候思路要清晰一点
for node.Next != nil {
node.Val = node.Next.Val
if node.Next.Next == nil {
node.Next = nil
}else {
node = node.Next
}
}
}
19. 删除链表倒数第N个节点
经典题总是容易出问题,不行就背过。定义一个哑节点,前指针指向dummy,后指针指向head,为什么这里要这样设置前指针呢,因为前指针要指向即将删除的结点的前一个结点,向后移动后指针N次,再同时移动前后指针,这样前指针就不会有空指针错误了。
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{0, head}
first,second := dummy,head
for i := 0; i < n; i++ {
second = second.Next
}
for ; second != nil; second = second.Next {
first = first.Next
}
first.Next = first.Next.Next
return dummy.Next
}
61. 旋转链表
这是有问题的代码,本来不该记录有问题的代码,记录已查看出现的问题。思路没什么问题,代码细节没处理好。
func getLength(head *ListNode) int {
var dummy *ListNode = &ListNode{0,head}
var length int = 0
for dummy != nil {
length++
dummy = dummy.Next
}
return length - 1
}
func rotateRight(head *ListNode, k int) *ListNode {
length := getLength(head)
if length == 0 {
return head
}
k = k % length
var dummy *ListNode = &ListNode{0,head}
var p *ListNode = dummy.Next
for i := 0;i < k;i++ {
p = p.Next
}
dummy.Next = p.Next
p.Next = nil
p = dummy.Next
for p.Next != nil {
p = p.Next
}
p.Next = head
return dummy.Next
}