leetcode-23-Merge k Sorted Lists-合并K个排序链表

帘外五更风 · · 769 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Merge k Sorted Lists

解题思路

链表两两合并,分而治之

代码-GoLang

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    p := list1
    q := list2
    var head, cur *ListNode
    var v int
    for p != nil || q != nil {
        if p == nil {
            v = q.Val
            q = q.Next
        } else if q == nil {
            v = p.Val
            p = p.Next
        } else {
            if q.Val < p. Val {
                v = q.Val
                q = q.Next
            } else {
                v = p.Val
                p = p.Next
            }
        }

        if head == nil {
            head = &ListNode{
                Val:v,
                Next:nil,
            }
            cur = head
        } else {
            cur.Next = &ListNode{
                Val:v,
                Next:nil,
            }
            cur = cur.Next
        }
    }
    return head
}

func merge(lists []*ListNode, st, en int) *ListNode {
    if st == en {
        return lists[st]
    }
    mid := st + (en - st + 1) / 2
    l1 := merge(lists, st, mid - 1)
    l2 := merge(lists, mid, en)
    return mergeTwoLists(l1, l2)
}

func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    return merge(lists, 0, len(lists) - 1)
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:帘外五更风

查看原文:leetcode-23-Merge k Sorted Lists-合并K个排序链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

769 次点击  
加入收藏 微博
上一篇:错误处理
下一篇:golang csv处理
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传