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
}

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

待复习

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

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

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

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

LC 142. 环形链表 II

待复习

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