链表
203. 移除链表元素
看完题目的第一想法
一道基本的链表题目，遍历链表如果当前节点的下一个节点值等于 val，那么就将当前节点的 Next指针指向下下一个节点。
如果要删除的值刚好位于头部，由于单链表没有指向头结点的指针，那么就需要单独处理头结点。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeElements(head *ListNode, val int) *ListNode {
// 处理头节点
for head != nil && head.Val == val {
head = head.Next
}
cur := head
// 处理后面的
for cur != nil && cur.Next != nil {
if cur.Next.Val == val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return head
}
进阶
处理链表另一种方法就是设置一个虚拟头结点，只需要让虚拟的头结点的 Next 指针指向 head，那么就可以保证逻辑处理的一致性。
注意的是：返回值需要返回的是dummyHead.Next。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeElements(head *ListNode, val int) *ListNode {
dummyHead := &ListNode{Next: head}
cur := dummyHead
for cur.Next != nil {
if cur.Next.Val == val {
cur.Next = cur.Next.Next
} else {
cur = cur.Next
}
}
return dummyHead.Next
}
今日收获
移除链表元素
- 首先想到的就是无头结点的方式遍历链表，然后单独处理头结点。
- 引入头结点可以是代码风格统一而且不需要单独处理头结点。
- 写代码时需要注意
cur := dummyHead，遍历时移动的是cur;
707. 设计链表
看完题目的第一想法
手写链表的一道题目，使用循环双向链表完成
- 在处理指定位置插入时，新插入的值应该在head 之前；
- 在处理指定位置删除时，head 为删除的元素，因此需要改变 head 的前后指针的指向。
type MyLinkedList struct {
dummy *Node
}
type Node struct {
Val int
Pre *Node
Next *Node
}
func Constructor() MyLinkedList {
node := &Node{
Val: -1,
Pre: nil,
Next: nil,
}
node.Next = node
node.Pre = node
return MyLinkedList{node}
}
func (m *MyLinkedList) Get(index int) int {
head := m.dummy.Next
for head != m.dummy && index > 0 {
head = head.Next
index--
}
if index != 0 {
return -1
}
return head.Val
}
func (m *MyLinkedList) AddAtHead(val int) {
dummy := m.dummy
node := &Node{
Val: val,
Pre: dummy,
Next: dummy.Next,
}
dummy.Next.Pre = node
dummy.Next = node
}
func (m *MyLinkedList) AddAtTail(val int) {
dummy := m.dummy
node := &Node{
Val: val,
Pre: dummy.Pre,
Next: dummy,
}
dummy.Pre.Next = node
dummy.Pre = node
}
func (m *MyLinkedList) AddAtIndex(index int, val int) {
head := m.dummy.Next
for head != m.dummy && index > 0 {
head = head.Next
index--
}
if index > 0 {
return
}
node := &Node{
Val: val,
Pre: head.Pre,
Next: head,
}
head.Pre.Next = node
head.Pre = node
}
func (m *MyLinkedList) DeleteAtIndex(index int) {
if m.dummy.Next == m.dummy {
return
}
head := m.dummy.Next
for head.Next != m.dummy && index > 0 {
head = head.Next
index--
}
// 当前的head为删除的节点
if index == 0 {
head.Next.Pre = head.Pre
head.Pre.Next = head.Next
}
}
附上单链表的代码:
type Node struct{
Val int
Next *Node
}
type MyLinkedList struct {
dummyhead *Node
size int
}
func Constructor() MyLinkedList {
return MyLinkedList{
dummyhead: &Node{
Val:-1,
Next: nil,
},
size:0,
}
}
func (c *MyLinkedList) Get(index int) int {
if index < 0 || index > c.size-1{
return -1
}
cur := c.dummyhead.Next
for index > 0{
cur = cur.Next
index--
}
return cur.Val
}
func (c *MyLinkedList) AddAtHead(val int) {
cur := c.dummyhead
node := &Node{
Val:val,
Next: cur.Next,
}
cur.Next = node
c.size++
}
func (c *MyLinkedList) AddAtTail(val int) {
cur := c.dummyhead
for cur.Next != nil{
cur = cur.Next
}
node := &Node{
Val:val,
Next: nil,
}
cur.Next = node
c.size++
}
func (c *MyLinkedList) AddAtIndex(index int, val int) {
if index > c.size{
return
}
cur := c.dummyhead
for index > 0 {
cur = cur.Next
index--
}
node := &Node{
Val:val,
Next: cur.Next,
}
cur.Next = node
c.size++
}
func (c *MyLinkedList) DeleteAtIndex(index int) {
if index <0 || index > c.size-1{
return
}
cur := c.dummyhead
for index > 0{
cur = cur.Next
index--
}
cur.Next = cur.Next.Next
c.size--
}
今日收获
练习了循环双向链表，还需要再多多练习
操作链表的指针时，需要注意前后的顺序，不要在已断开的指针上再进行操作
206.反转链表
看完题目的第一想法
反转单链表只需要改变指针 next 的指向即可
使用双指针的解法:
- 首先使用变量
tmp指向cur.Next - 改变
cur.Next指针指向 - 让pre向前走，移动到cur的位置
- cur 向前走，走到下一个位置（注意不能使用
cur.Next，因为cur.Next此时指向已经发生了改变）
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
// pre 指向空结点， cur指向头结点
var pre *ListNode
cur := head
for cur != nil{
tmp := cur.Next
cur.Next = pre
pre = cur
cur = tmp
}
return pre
}
使用递归的解法
- 递归的返回值就是链表的头结点
- 递归函数
reverse(pre,cur)可以理解成pre = cur; cur = tmp,与双指针的解法逻辑相同
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var reverse func(*ListNode, *ListNode) *ListNode
reverse = func(pre, cur *ListNode) *ListNode {
if cur == nil {
return pre
}
tmp := cur.Next
cur.Next = pre
return reverse(cur, tmp)
}
return reverse(nil, head)
}
今日收获
反转链表比较容易， 了解双指针的解法后递归的写法也比较容易理解了。
标签：index,head,ListNode,cur,int,第三天,Next,链表,算法 From： https://www.cnblogs.com/neilliu/p/16724549.html