首页 > 其他 > 详细

(链表)链表的一些合并问题

时间:2017-02-03 20:43:26      阅读:266      评论:0      收藏:0      [点我收藏+]
  • 问题一:合并两个排序的链接列表,并将其作为新列表返回。 新列表应该通过将前两个列表的节点拼接在一起来进行。
  • 思路:有两种方式:递归和非递归。我感觉递归的比较简单。给定两个链表,如果l1为空,返回l2,如果l2为空,返回l1.
      如果l1节点大于l2,node等于l2当前节点,node->next=(递归调用函数处理)merge(l1,l2->next);
  • 代码:
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            // head1为空,返回head2
            if(l1 == NULL) return l2;
            // head2为空,返回head1
            if(l2 == NULL) return l1;
            // 记录合并链表
            ListNode *node = NULL;
            if(l1->val > l2->val) {
                node = l2;
                node->next = mergeTwoLists(l1, l2->next);
            } else {
                node = l1;
                node->next = mergeTwoLists(l1->next, l2);
            }
            return node;
        }
    };

     当然也可以在原链表的基础上面直接合并。

  • 问题二:合并多个已经排序的链表,合并k个已排序的链表,并将其作为一个排序列表返回。 分析和描述其复杂性。
  • 思路:这个可以两个两个链表进行合并,从头开始合并,合并完的将其出列,最后容器中就剩一个已经完全排序的链表。
  • 代码
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode *node = NULL;
        ListNode *mergeKLists(vector<ListNode *> &lists) {
            if (lists.size() < 1)
                return NULL;
            while (lists.size()-1){
                   lists.push_back(mergeTwoLists(lists[0], lists[1]));
                   lists.erase(lists.begin());
                lists.erase(lists.begin());
            }
            return lists.front();
        }
        ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
            // head1为空,返回head2
            if(l1 == NULL) return l2;
            // head2为空,返回head1
            if(l2 == NULL) return l1;
            // 记录合并链表
            if(l1->val > l2->val) {
                l2->next = mergeTwoLists(l1, l2->next);
                return l2;
            } else {
                l1->next = mergeTwoLists(l1->next, l2);
                return l1;
            }
        }
    };

     

(链表)链表的一些合并问题

原文:http://www.cnblogs.com/Kobe10/p/6363321.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!