Leetcode 链表

交换相邻链表

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

这道题 要理解 相邻链表的交换条件以及cur节点遍历整个链表的条件

• 如果是奇数链表 则当链表的current的下下个next指向为NULL,则遍历结束
• 如果是偶数链表 则当链表的current的下个next指向为NULL 则遍历结束

对于第一次遍历 在设置虚拟头节点之后 我们一共三个步骤

1. 将虚拟头节点指向第二个节点值

2. 交换第一和第二节点值（交换相邻节点值）

3. 交换后指向第三个节点

   如此循环，因为每个元素只被操作一次 则时间复杂度为O(n)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    dummyHead := &ListNode{
        Next: head,
    }

    cur := dummyHead
    for cur.Next!=nil && cur.Next.Next!=nil{
        
        temp := cur.Next //临时节点 保存前一个节点
        temp1 := cur.Next.Next.Next
        cur.Next = cur.Next.Next
        cur.Next.Next = temp
        temp.Next=temp1
        
        cur = cur.Next.Next

    }
    return dummyHead.Next

}

删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

• 第一种方法

  • 先获取链表的长度 length 然后倒数第n个节点就是 length-n+1 的长度

  • 然后遍历链表到length-n+1 跳过节点 即可

  • ```go
    func getLength(head *ListNode)(length int){

    for head!=nil{
        head = head.Next
        length ++
    }
    return 
    

    }//获取链表长度

    func removeNthFromEnd(head ListNode, n int) ListNode {

    length := getLength(head)
    dummy := &ListNode{0, head}
    cur := dummy
    for i := 0; i < length-n; i++ {
        cur = cur.Next
    }
    cur.Next = cur.Next.Next
    return dummy.Next
    

    }

        对于第一种方法，其实相当于遍历了两遍链表 时间复杂度是O(n)
    
    - ### 双指针
    
      - 设置两个指针 且快慢指针之间相差的节点数为n,那么对于快指针来讲说 当他遍历到链表末尾的时候，慢指针刚好遍历到倒数第n个节点的位置
      - <img src="https://assets.leetcode-cn.com/solution-static/19/p3.png" style="zoom: 67%;" />
      - 对于整个模拟过程来说 ，首先初始是**second**指针位于dummy节点，**first**节点位于head节点位置，
      - **对first指针先遍历到n**这样 快指针和慢指针之间相差了n个节点
      - 然后对慢指针进行遍历 遍历条件是慢指针遍历的同时，快指针跟着遍历，这样就一直相差n个节点 直到快指针遍历链表结束
    
    ```go
    func removeNthFromEnd(head *ListNode, n int) *ListNode {
        dummy := &ListNode{0, head}
        first, second := head, dummy
        for i := 0; i < n; i++ {
            first = first.Next
        }
        for ; first != nil; first = first.Next {
            second = second.Next
        }
        second.Next = second.Next.Next
        return dummy.Next
    }

环形链表

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况

• 第一种方法

  • 哈希表存取 直接遍历整个链表

  • 判断出相同元素出现在链表中 则证明链表成环

  • ```go
    func detectCycle(head ListNode) ListNode {

    seen := map[*ListNode]struct{}{}
    for head != nil {
        if _, ok := seen[head]; ok {
            return head
        }
        seen[head] = struct{}{}
        head = head.Next
    }
    return nil
    

    }

    - ### 第二种方法（双指针）
    
      - **首先要判断链表中是否有环**
    
        - 使用快慢指针 ，当快慢指针相遇时则代表链表中有环
        - 对于快指针 **fast** 设定为速度为**两个节点**，对于慢指针 **slow** 设定速度为**一个节点** ，则快慢指针的速度差为 **一个节点** 那么当指针遍历链表的时候，一定是快指针先入环，然后慢指针后入，此时 **相当于快指针以一个节点的速度 追赶慢指针**  直到相遇
    
      - **怎样判定环的入口**
    
        - <img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20220925103433.png" style="zoom: 50%;" />
    
        - 那么相遇时： slow指针走过的节点数为: `x + y`， fast指针走过的节点数：`x + y + n (y + z)`，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
    
          因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

    (x + y) * 2 = x + y + n (y + z)

      两边消掉一个（x+y）: `x + y = n (y + z)`
    
      因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
    
      所以要求x ，将x单独放在左面：`x = n (y + z) - y` ,
    
      再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：`x = (n - 1) (y + z) + z` 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
    
    - 当 n为1的时候，公式就化解为 `x = z`，
    
      这就意味着，**从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点**。
    
      也就是在相遇节点处，定义一个指针**index1**，在头结点处定一个指针**index2**。
    
      让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
    
      
    
      ```go
      func detectCycle(head *ListNode) *ListNode {
          fast := head //设置快指针
          slow := head//设置慢指针
          for fast != nil && fast.Next != nil {
              fast = fast.Next.Next //快指针向前遍历
              slow = slow.Next//慢指针向前遍历
              if fast == slow {// 快慢指针相遇条件
                  index1 := fast
                  index2 := head
                  for index1 != index2{  // index 指针 同时移动 当相遇时 即是环的入口
                      index1 = index1.Next
                      index2 = index2.Next
                  }
                  return index1 //返回环的如果
              }
          }
          return nil //如果不存在，就返回nil
      }

​