203. 移除链表元素

• 递归方法

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    head.Next = removeElements(head.Next, val)
    if head.Val == val {
        return head.Next
    }
    return head
}

• 非递归

func removeElements(head *ListNode, val int) *ListNode {
    node := head // 定一个游标头节点
    for node.Next != nil {
        if node.Next.Val == val {
            temp := node.Next
            node.Next = temp.Next
        }
        node = node.Next // 油标后移
    }
    return head
}

链表的工具方法

// 链表定义
type ListNode struct {
    Val  int
    Next *ListNode
}

// 数组转链表的工具
func createLinkedList(values []int) *ListNode {
    head := &ListNode{}
    curr := head

    for _, val := range values {
        curr.Next = &ListNode{Val: val}
        curr = curr.Next
    }

    return head.Next
}
// 链表转数组
func ListNode2arr(head *ListNode) []any {
    var res []any
    node := &ListNode{-1, head} // 定一个油标头节点
    for node.Next != nil {
        res = append(res, node.Next.Val)
        node = node.Next
    }
    return res
}

707. 设计链表

// 单链表
type MyLinkedList struct {
    val  int           // 节点值
    next *MyLinkedList // 下一个节点指针
    //prev *MyLinkedList // 上一个节点指针
}

var head MyLinkedList // 头节点
var length int

func Constructor() MyLinkedList {
    head = MyLinkedList{}
    length = 0
    return head // 返回一个头节点
}

func (this *MyLinkedList) Get(index int) int {
    if index >= length || index < 0 {
        return -1
    }
    node := this
    for i := 0; i < index; i++ {
        node = node.next
    }
    return node.next.val
}

func (this *MyLinkedList) AddAtHead(val int) {
    temp := this.next
    newNode := MyLinkedList{val: val, next: temp}
    this.next = &newNode
    length++
}

func (this *MyLinkedList) AddAtTail(val int) {
    newNode := MyLinkedList{val: val, next: nil}
    node := this
    for node.next != nil {
        node = node.next
    }
    node.next = &newNode
    length++
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
    // 合法检测
    if index > length || index < 0 {
        return
    }
    if index == length {
        this.AddAtTail(val)
        return
    }

    // 找到下标为index的节点
    cur := this
    for i := 0; i < index; i++ {
        cur = cur.next
    }

    // 头插
    newNode := MyLinkedList{val: val, next: cur.next}
    cur.next = &newNode
    length++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
    // 合法检测
    if index >= length || index < 0 {
        return
    }
    node := this
    for i := 0; i < index; i++ {
        node = node.next
    }
    temp := node.next
    node.next = temp.next

    length--
}

206. 反转链表

• 头插法(原地逆转)

func headInsert(head *ListNode, node *ListNode) {
    node.Next = head.Next
    head.Next = node
}

func reverseList(head *ListNode) *ListNode {
    var newHead ListNode
    cur := head // 游标

    for cur != nil {
        temp := cur
        cur = cur.Next
        headInsert(&newHead, temp)
    }
    return newHead.Next
}

• 递归（栈）
  

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead

}

• 新节点复制
  ...

---

• 分类： 算法
• 标签： 算法基础 单链表