链表总结

链表的合并

• 虚拟头节点
• 拉拉链

  func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
      // 虚拟头结点
      dummy := &ListNode{-1, nil}
      p := dummy
      p1 := l1
      p2 := l2
      
      for p1 != nil && p2 != nil {
          // 比较 p1 和 p2 两个指针
          // 将值较小的的节点接到 p 指针
          if p1.Val > p2.Val {
              p.Next = p2
              p2 = p2.Next
          } else {
              p.Next = p1
              p1 = p1.Next
          }
          // p 指针不断前进
          p = p.Next
      }
      
      if p1 != nil {
          p.Next = p1
      }
      
      if p2 != nil {
          p.Next = p2
      }
      
      return dummy.Next
  }

链表的拆分

• 初始化两个链表，分别添加
• 合并前 记得 将p.next 置为空，防止后边p1.next 还挂着p.next
• 合并

func partition(head *ListNode, x int) *ListNode {
    // 存放小于 x 的链表的虚拟头结点
    dummy1 := &ListNode{-1, nil}
    // 存放大于等于 x 的链表的虚拟头结点
    dummy2 := &ListNode{-1, nil}
    // p1, p2 指针负责生成结果链表
    p1, p2 := dummy1, dummy2
    // p 负责遍历原链表，类似合并两个有序链表的逻辑
    // 这里是将一个链表分解成两个链表
    p := head
    for p != nil {
        if p.Val >= x {
            p2.Next = p
            p2 = p2.Next
        } else {
            p1.Next = p
            p1 = p1.Next
        }
        // 断开原链表中的每个节点的 next 指针
        temp := p.Next
        p.Next = nil
        p = temp
    }
    // 连接两个链表
    p1.Next = dummy2.Next

    return dummy1.Next
}

k 链表合并

• 最小堆 go语言的实现

type ListNode struct {
    Val int
    Next *ListNode
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    // 虚拟头结点
    dummy := &ListNode{-1, nil}
    p := dummy
    // 优先级队列，最小堆
    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    // 将 k 个链表的头结点加入最小堆
    for _, head := range lists {
        if head != nil {
            heap.Push(&pq, head)
        }
    }

    for pq.Len() > 0 {
        // 获取最小节点，接到结果链表中
        node := heap.Pop(&pq).(*ListNode)
        p.Next = node
        if node.Next != nil {
            heap.Push(&pq, node.Next)
        }
        // p 指针不断前进
        p = p.Next
    }
    return dummy.Next
}

type PriorityQueue []*ListNode

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    node := x.(*ListNode)
    *pq = append(*pq, node)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    node := old[n-1]
    *pq = old[0 : n-1]
    return node
}

倒数K链表

• n 是包含nil 的
• 一个fast 去探路，先走k步
• slow 和fast 一起走
• 当fast为nil 时，到达k ,赋值为next.next 即可
  

// 主函数
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 虚拟头结点
    dummy := &ListNode{-1, head}
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    x := findFromEnd(dummy, n + 1)
    // 删掉倒数第 n 个节点
    x.Next = x.Next.Next
    return dummy.Next
}
    
// 返回链表的倒数第 k 个节点
func findFromEnd(head *ListNode, k int) *ListNode {
    p1 := head
    // p1 先走 k 步
    for i := 0; i < k; i++ {
        p1 = p1.Next
    }
    p2 := head
    // p1 和 p2 同时走 n - k 步
    for p1 != nil {
        p1 = p1.Next
        p2 = p2.Next
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2
}

倒数K链表移除

复用上边的代码，找到倒数x=k+1, 然后赋值x.next = x.next.next 即可

// 主函数
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 虚拟头结点
    dummy := &ListNode{-1, head}
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    x := findFromEnd(dummy, n + 1)
    // 删掉倒数第 n 个节点
    x.next = x.next.next
    return dummy.next
}
    
func findFromEnd(head *ListNode, k int) *ListNode {
    // 代码见上文
}

移除中间链表

876. 链表的中间结点 - 力扣（LeetCode）

• slow 走一步，fast走两步
• fast nil，slow 为中间
  每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

func middleNode(head *ListNode) *ListNode {
    // 快慢指针初始化指向 head
    slow, fast := head, head
    // 快指针走到末尾时停止
    // for fast.Next != nil && fast.Next.Next != nil {// 这样奇数的时候会在中点的前一步
    for fast!= nil && fast.Next != nil{ // 应该修改为这个，slow 会停在中点右边第二个部分
        // 慢指针走一步，快指针走两步
        slow = slow.Next
        fast = fast.Next.Next
    }
    // 慢指针指向中点
    return slow
}

判断链表是否成环

• slow 走一步，fast走两步
• fast 和slow 相遇则成环，fast 遇到nil 则不成环。

func hasCycle(head *ListNode) bool {
    // 快慢指针初始化指向 head
    slow, fast := head, head
    // 快指针走到末尾时停止
    for fast != nil && fast.Next != nil {
        // 慢指针走一步，快指针走两步
        slow = slow.Next
        fast = fast.Next.Next
        // 快慢指针相遇，说明含有环
        if slow == fast {
            return true
        }
    }
    // 不包含环
    return false
}

labuladong