链表的合并
- 虚拟头节点
- 拉拉链
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{-1, nil} p := dummy p1 := l1 p2 := l2 for p1 != nil && p2 != nil { if p1.Val > p2.Val { p.Next = p2 p2 = p2.Next } else { p.Next = p1 p1 = p1.Next } p = p.Next } if p1 != nil { p.Next = p1 } if p2 != nil { p.Next = p2 } return dummy.Next }
|
链表的拆分
- 初始化两个链表,分别添加
- 合并前 记得 将p.next 置为空,防止后边p1.next 还挂着p.next
- 合并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| func partition(head *ListNode, x int) *ListNode { dummy1 := &ListNode{-1, nil} dummy2 := &ListNode{-1, nil} p1, p2 := dummy1, dummy2 p := head for p != nil { if p.Val >= x { p2.Next = p p2 = p2.Next } else { p1.Next = p p1 = p1.Next } temp := p.Next p.Next = nil p = temp } p1.Next = dummy2.Next
return dummy1.Next }
|
k 链表合并
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
| 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) 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.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 即可

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{-1, head} x := findFromEnd(dummy, n + 1) x.Next = x.Next.Next return dummy.Next }
func findFromEnd(head *ListNode, k int) *ListNode { p1 := head for i := 0; i < k; i++ { p1 = p1.Next } p2 := head for p1 != nil { p1 = p1.Next p2 = p2.Next } return p2 }
|
倒数K链表移除
复用上边的代码,找到倒数x=k+1, 然后赋值x.next = x.next.next 即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func removeNthFromEnd(head *ListNode, n int) *ListNode { dummy := &ListNode{-1, head} x := findFromEnd(dummy, n + 1) 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
就指向了链表中点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| func middleNode(head *ListNode) *ListNode { slow, fast := head, head for fast!= nil && fast.Next != nil{ slow = slow.Next fast = fast.Next.Next } return slow }
|
判断链表是否成环
- slow 走一步,fast走两步
- fast 和slow 相遇则成环,fast 遇到nil 则不成环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| func hasCycle(head *ListNode) bool { 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