9.代码随想录-链表（上）

一、移除链表元素 

��       题干：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

        测试地址：. - 力扣（LeetCode）

        操作原链表

        首先让头结点进行遍历，找到第一个节点的Val不为val的节点作为头结点。然后设置变量cur指向head，随后进行遍历。同时这里for cur != nil && cur.Next != nil 必须加上cur!=nil的原因是head可能指向nil，然后让cur指向head并操作cur.Next是会报错的。或者在cur赋值语句前加上对head == nil的判断，如果是则return，也可以通过测试。

        核心：时刻注意不要操作空指针

func removeElements(head *ListNode, val int) *ListNode {for head != nil && head.Val == val {head = head.Next}cur := headfor cur != nil && cur.Next != nil {if cur.Next.Val == val {cur.Next = cur.Next.Next} else {cur = cur.Next}}return head}

        虚拟头结点

        在原链表上操作首先是要找到第一个值不为val的节点，然后以此为头再进行遍历操作。而如果使用虚拟头结点，换言之直接找到了第一个不为val的节点，直接对后续进行遍历即可。最后返回的之后返回虚拟头结点的next即可。

func removeElements(head *ListNode, val int) *ListNode {dummy := &ListNode{}dummy.Next = headcur := dummyfor cur.Next != nil {if cur.Next.Val == val {cur.Next = cur.Next.Next}else {cur = cur.Next}}return dummy.Next}

 二、设计链表

        题干：

        在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

          测试地址：. - 力扣（LeetCode）

          这里好像必须要用虚拟头结点法，不然因为go语言中的引用传递也不过是拷贝一份指针指向堆中变量的位置，所以没有办法对原始指针进行更改，所以这里的addAtHead没有办法更新，当然在自己的代码里面可以通过

  a = a.AddAtHead(7)

          进行更改，但是在lc里面不会这样进行操作，所以过不了检测。但是也有一种方案是在头结点之后插入节点，然后把它的值和头结点的值进行互换，这里是采用了这种方式

  非虚拟头结点：

  func Constructor() MyLinkedList {return MyLinkedList{}}func (this *MyLinkedList) Get(index int) int {node := thisfor i := 0; i  index {last := thiscur = thisfor i := 0; i  this.Size { // 如果索引大于链表长度，直接返回return}newNode := &SingleNode{Val: val} // 创建新节点cur := this.dummyHead            // 设置当前节点为虚拟头节点for i := 0; i = this.Size { // 如果索引无效则直接返回return}cur := this.dummyHead        // 设置当前节点为虚拟头节点for i := 0; i   
  三、反转链表
   
          题干：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
   
          测试地址：. - 力扣（LeetCode）
   
          思路很简单，就是本来节点1连向节点2，现在让节点1指向空，节点2指向节点1即可，但是这样的问题会是如果后面有节点3，那不就找不到节点3了吗，所以需要多用一个变量即可。
   
          循环版本
     
   func reverseList(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}var last, cur  *ListNodelast, cur = nil, headfor cur != nil {next := cur.Nextcur.Next = lastlast = curcur = next}return last}
    
          递归版本
     
  func reverseList(head *ListNode) *ListNode {return reverse(nil, head)}func reverse(last, cur *ListNode) *ListNode {if cur == nil {return last}next := cur.Nextcur.Next = lastreturn reverse(cur, next)}
    
  四、两两交换链表中的节点
   
          题干：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
   
          测试地址：. - 力扣（LeetCode）
   
          建议画图，还是比较好搞懂的。虚拟头结点法确实是好用的。
     
  func swapPairs(head *ListNode) *ListNode {if head == nil || head.Next == nil {return head}dummy := &ListNode{Next: head}cur := dummyfor cur.Next != nil && cur.Next.Next != nil {temp := cur.Nextcur.Next = temp.Nextcur = temp.Nexttemp.Next = cur.Nextcur.Next = temp        cur = temp}return dummy.Next}