Blog

leetcode23合并K个排序链表

leetcode23 Merge k Sorted Lists

Posted by BY on August 1, 2018

前言

一个continue写成break导致问题找了好久

正文

问题来源

本问题来自leetcode上的23题。用go语言做的

问题描述

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例 1:

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:

输入:  
[
  1->4->5,  
  1->3->4,  
  2->6  
]  
输出: 1->1->2->3->4->4->5->6

分析：

暴力解法(自然是我自己想到的，总是不想最优解法) Go代码如下：

func mergeKLists(lists []*ListNode) *ListNode {
	head := &ListNode{0, nil} 
	q := head
	if lists == nil {
		return nil
	}
	var nilCount int
	len := len(lists)
	var min int
	var minIndex int
	for {
		nilCount = 0
		i := 0
		for ; i < len; i++ {
			if nil == lists[i] {
				nilCount++
				continue
			} else {
				min = lists[i].Val
				minIndex = i
				break
			}
		}
		if nilCount == len {
			break
		}
		j := i
		for ; j < len; j++ {
			if nil == lists[j] {
				continue
			} else if min > lists[j].Val {
				min = lists[j].Val
				minIndex = j
			}
		}
		q.Next = lists[minIndex]
		q = q.Next
		lists[minIndex] = lists[minIndex].Next
	}
	return head.Next
}

其实这道题应该用分治来解（别人家的代码）

func doMerge(l1, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    
    if l2 == nil {
        return l1
    }
    
    var h *ListNode
    var prev *ListNode
    
    for l1 != nil && l2 != nil {
        var node *ListNode
        if l1.Val <= l2.Val {
            node = l1
            l1 = l1.Next
        } else {
            node = l2
            l2 = l2.Next
        }
        
        if prev == nil {
            h = node
            prev = node
        } else {
            prev.Next = node
            prev = node
        }
    }
    
    if l1 != nil {
        prev.Next = l1
    } else if l2 != nil {
        prev.Next = l2
    }
    
    return h
}
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    
    for {
        if len(lists) == 1 {
            return lists[0]
        }

        next := make([]*ListNode, 0)
        var i = 0
        for i = 1; i < len(lists); i = i + 2 {
            node := doMerge(lists[i-1], lists[i])
            next = append(next, node)
        }
        
        if len(lists) % 2 != 0 {
            next = append(next, lists[len(lists)-1])
        }
        
        lists = next
    }
    
}

总结：

多思考是否有简单并且高效的解法

结语

闲来无事的话，多练习练习，做做题。

CATALOG
    FEATURED TAGS
    Blog