Week 48 @ 2024 算法周记【双指针链表】

1 LC 21. Merge Two Sorted Lists 合并两个有序链表
2 LC 86. Partition List 分隔链表
3 LC 23. Merge k Sorted Lists 合并 K 个有序链表
4 LC 19. Remove Nth Node From End of List 删除链表的倒数第 N 个节点
5 LC 876. Middle of the Linked List 链表的中间节点
6 LC 142. 环形链表 II

LC 21. Merge Two Sorted Lists 合并两个有序链表

https://leetcode.com/problems/merge-two-sorted-lists/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    h := dummy
    
    h1, h2 := list1, list2
    
    for h1 != nil && h2 != nil {
        if h1.Val < h2.Val {
            h.Next = h1
            h1 = h1.Next
            h = h.Next
        } else {
            h.Next = h2
            h2 = h2.Next
            h = h.Next
        }
    }
    
    for h1 != nil {
        h.Next = h1
        h1 = h1.Next
        h = h.Next
    }
    
    for h2 != nil {
        h.Next = h2
        h2 = h2.Next
        h = h.Next
    }
    
    return dummy.Next
}

LC 86. Partition List 分隔链表

https://leetcode.com/problems/partition-list/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    dummy1, dummy2 := &ListNode{}, &ListNode{}
    h1, h2 := dummy1, dummy2
    
    for head != nil {
        if head.Val < x {
            h1.Next = head
            h1 = h1.Next
            head = head.Next 
        } else {
            h2.Next = head
            h2 = h2.Next
            head = head.Next
        }
    }
    
    h1.Next = dummy2.Next
    h2.Next = nil
    
    return dummy1.Next
}

LC 23. Merge k Sorted Lists 合并 K 个有序链表

https://leetcode.com/problems/merge-k-sorted-lists/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    dummy := &ListNode{}
    h := dummy
    
    for {
        minValue := 10_0000
        minValuePI := -1
        for i, h := range lists {
            if h != nil {
                if h.Val < minValue {
                    minValue = h.Val
                    minValuePI = i
                }
            }
        }
        
        if minValuePI == -1 {
            break
        } else {
            h.Next = lists[minValuePI]
            h = h.Next
            lists[minValuePI] = lists[minValuePI].Next
        }
    }
    
    h.Next = nil
    
    return dummy.Next
}

利用最小堆优化时间复杂度

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    dummy := &ListNode{}
    p := dummy
    
    h := NodeHeap{}
    
    for _, l := range lists {
        p := l
        for p != nil {
            heap.Push(&h, p)
            p = p.Next
        }
    }
    
    for len(h) > 0 {
        node := heap.Pop(&h).(*ListNode)
        p.Next = node
        p = p.Next
    }
    
    p.Next = nil
   
    return dummy.Next
}

type NodeHeap []*ListNode

func (h NodeHeap) Len() int {
    return len(h)
}
func (h NodeHeap) Less(i, j int) bool {
    return h[i].Val < h[j].Val
}
func (h NodeHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h *NodeHeap) Push(x any) {
    *h = append(*h, x.(*ListNode))
}
func (h *NodeHeap) Pop() any {
    node := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    
    return node
}

LC 19. Remove Nth Node From End of List 删除链表的倒数第 N 个节点

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head}
    p := getNthFromEnd(dummy, n+1)
    
    p.Next = p.Next.Next
    
    return dummy.Next
}

func getNthFromEnd(head *ListNode, c int) *ListNode {
    slow, fast := head, head
    for i := 0; i < c; i++ {
        fast = fast.Next
    }
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

LC 876. Middle of the Linked List 链表的中间节点

https://leetcode.com/problems/middle-of-the-linked-list/description/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

LC 142. 环形链表 II

待复习

https://leetcode.com/problems/linked-list-cycle-ii/description/

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        
        if slow == fast {
            break
        }
    }
    
    if fast == nil || fast.Next == nil {
        return nil // no cycle
    }
    
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    
    return fast
}

知识库

Week 48 @ 2024 算法周记【双指针链表】

LC 21. Merge Two Sorted Lists 合并两个有序链表

LC 86. Partition List 分隔链表

LC 23. Merge k Sorted Lists 合并 K 个有序链表

LC 19. Remove Nth Node From End of List 删除链表的倒数第 N 个节点

LC 876. Middle of the Linked List 链表的中间节点

LC 142. 环形链表 II

Related content