代码随想录算法训练营第4天 | lc24、lc19、lc面试题02.07、lc142

（本合集全部为Go语言实现）

相关文章链接：24题解 19题解 02.07题解 142题解
相关视频链接：

Leetcode24

状态：秒了
实现过程中的难点：对组内两个节点的指针指向流转需要倒腾明白。临时头结点真的很有用

个人写法

func swapPairs(head *ListNode) *ListNode {
  tmpHead := &ListNode{-1, head}
  ptr := tmpHead
  for ptr.Next != nil && ptr.Next.Next != nil {
    tmp := ptr.Next
    ptr.Next = tmp.Next
    tmp.Next = tmp.Next.Next
    ptr.Next.Next = tmp
    ptr = ptr.Next.Next
  }
  return tmpHead.Next
}

Leetcode19

状态：秒了
实现过程中的难点：需要自己模拟出最终状态，确保左指针是待删除节点的前一个节点

个人写法

func removeNthFromEnd(head *ListNode, n int) *ListNode {
  tmpHead := &ListNode{-1, head}
  post := tmpHead
  pre := tmpHead
  for i := 0; i < n; i++ {
    pre = pre.Next
  }
  for pre.Next != nil {
    pre = pre.Next
    post = post.Next
  }
  post.Next = post.Next.Next
  return tmpHead.Next
}

Leetcode面试题02.07

状态：改了几次，有些情况没考虑到位
实现过程中的难点：主要是巧妙写法的思路能不能想出来

个人写法

暴力写法应该是同步遍历两各分支，并同时将分支节点指针存到Set中，如果其中一个分支的指针在另一个分支的Set中出现了，那么该节点就是相交点

func getIntersectionNode(headA, headB *ListNode) *ListNode {
  if headA == nil || headB == nil {
    return nil
  } 
  ptr1, ptr2 := headA, headB
  for ptr1 != ptr2 {
    if ptr1 == nil {
      ptr1 = headB
    } else {
      ptr1 = ptr1.Next
    }
    if ptr2 == nil {
      ptr2 = headA
    } else {
      ptr2 = ptr2.Next
    }
  }
  return ptr1
}

Leetcode142

状态：记得这道是快慢指针，但是忘了过程是怎么写的了。看了代码随想录的B站视频复习了一下
实现过程中的难点：其实是数学问题，直接想不太好想，需要基于数学公式模拟过程

过程分析

快慢指针过程推导：两个指针初始状态都指向头节点，fast指针每次走两步，slow指针每次走一步

判断链表是否有环

• 由于fast一定在前，所以如果fast先探测到空，那么链表一定无环
• 如果链表有环，那么两指针一定会进入环，此时fast相对slow的速度为1，所以两者最终一定会相遇，而不会出现fast跳过slow的情景。这可能起初看到此题的一个疑问

环入口点的搜索

设无环部分长度为x，环内部分中，入口到相遇点长度为y，相遇点距离入口点长度为z

• 由快慢指针之间的速度关系可以得到：2 * (x + y) = x + y + k * (y + z)
  • 推导得：x = (k - 1) * y + k * z
  • 为什么有个参数k？你可能会认为，从慢指针进入环到两者相遇，快指针可能是在走了k圏之后，才和慢指针相遇的，但是此时慢指针已经进入环了，首次相遇就会跳出循环，所以k = 1
  • 于是x = z，这就是结题的关键条件了

个人写法

func detectCycle(head *ListNode) *ListNode {
  if head == nil || head.Next == nil {
    return nil
  }
  fast, slow := head.Next.Next, head.Next
  for fast != slow {
    if fast == nil || fast.Next == nil {
      return nil
    }
    fast = fast.Next.Next
    slow = slow.Next
  }
  fast = head
  for fast != slow {
    fast = fast.Next
    slow = slow.Next
  }
  return fast
}

今日收获

• 主要是最后一道题的思路没有想到，算是复习了一下

学习时长：2小时左右比较分散