22,23合并K个链表链表

淩亂°似流年 2022-10-18 11:30 19阅读 0赞

# 21. [合并两个有序链表][Link 1] #

迭代法

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
    func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { 
        l3 := new(ListNode)
        head := l3
        for l1!=nil && l2 != nil{ 
            if l1.Val > l2.Val{ 
                l3.Next =l2
                l2 = l2.Next
            }else{ 
                l3.Next =l1
                l1 = l1.Next
            }
            l3 = l3.Next
        }
        if l1 !=nil{ 
            l3.Next = l1
        }
        if l2 !=nil{ 
            l3.Next = l2
        }
        return head.Next
    }

# [23. 合并K个链表][23. _K] #

分治 , 然后进行合并

class Solution { 
        public ListNode mergeKLists(ListNode[] lists) { 
            return merge(lists, 0, lists.length - 1);
        }
    
        public ListNode merge(ListNode[] lists, int l, int r) { 
            if (l == r) { 
                return lists[l];
            }
            if (l > r) { 
                return null;
            }
            int mid = (l + r) >> 1;
            return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
        }
    
        public ListNode mergeTwoLists(ListNode a, ListNode b) { 
            if (a == null || b == null) { 
                return a != null ? a : b;
            }
            ListNode head = new ListNode(0);
            ListNode tail = head, aPtr = a, bPtr = b;
            while (aPtr != null && bPtr != null) { 
                if (aPtr.val < bPtr.val) { 
                    tail.next = aPtr;
                    aPtr = aPtr.next;
                } else { 
                    tail.next = bPtr;
                    bPtr = bPtr.next;
                }
                tail = tail.next;
            }
            tail.next = (aPtr != null ? aPtr : bPtr);
            return head.next;
        }
    }

分治, 然后两两合并

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */
    func mergeKLists(lists []*ListNode) *ListNode { 
        return merge(lists, 0, len(lists)-1)
    }
    
    func merge(lists []*ListNode,left ,right int) *ListNode { 
        if left == right { 
            return lists[left]
        }
        if left > right { 
            return nil
        }
        mid := (left + right)>>1
        return mergeTwoLists(merge(lists,left,mid),merge(lists,mid+1,right))
    }
    
    func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode { 
        l3 := new(ListNode)
        head := l3
        for l1!=nil && l2 != nil{ 
            if l1.Val > l2.Val{ 
                l3.Next =l2
                l2 = l2.Next
            }else{ 
                l3.Next =l1
                l1 = l1.Next
            }
            l3 = l3.Next
        }
        if l1 !=nil{ 
            l3.Next = l1
        }
        if l2 !=nil{ 
            l3.Next = l2
        }
        return head.Next
    }

[Link 1]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[23. _K]: https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/