1, 题目描述:
将两个有序链表合并为一个新的有序链表并返回. 新链表是通过拼接给定的两个链表的所有节点组成的.
示例:
输入: 1->2->4, 1->3->4
输出: 1->1->2->3->4->4
2, 想法:
假设一个头结点 "prehead"(最后可以比较容易返回合并后的链表), 并且维护一个 prev 指针, 我们需要做的是调整它的 next 指针.
重复过程如下: 如果 l1 当前的位置小于 l2, 就把 l1 的值接到 prev 节点后面同时将 l1 往后移动一个; 否则对 l2 做同样的操作. 不管把哪
一个元素接在了 prev 的后面, 都要把 prev 往后移动一个元素. 重复该过程直到 l1 或者 l2 指向了 NULL.
注意: 循环结束后, l1 和 l2 至多有一个非空的, 由于 l1 和 l2 本身就是有序的, 所以不管剩的是哪个链表, 都可以简单地把他接到 prev(合并链)
后面, 最后返回合并链就行了.
3, 代码
- /**C++
- * 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) {
- if (!l1) return l2;
- if (!l2) return l1;
- ListNode* l3 = new ListNode(-1);
- ListNode* p = l3, *q;
- while(l1 && l2)
- {
- if (l1->val <l2->val)
- {
- q = new ListNode(l1->val);
- p->next = q;
- p = q;
- l1 = l1->next;
- }
- else
- {
- q = new ListNode(l2->val);
- p->next = q;
- p = q;
- l2 = l2->next;
- }
- }
- if (l1) l2 = l1;
- p->next = l2;
- return l3->next;
- }
- };
- View Code
- # Definition for singly-linked list.
- # class ListNode(object):
- # def __init__(self, x):
- # self.val = x
- # self.next = None
- class Solution(object):
- def mergeTwoLists(self, l1, l2):
- """
- :type l1: ListNode
- :type l2: ListNode
- :rtype: ListNode
- """""" 递归做法 """
- if l1 is None: return l2
- if l2 is None: return l1
- elif l1.val < l2.val:
- l1.next = self.mergeTwoLists(l1.next, l2)
- return l1
- else:
- l2.next = self.mergeTwoLists(l1, l2.next)
- return l2
- """
- prehead = ListNode(-1)
- prev = prehead
- while l1 and l2:
- if l1.val <= l2.val:
- prev.next = l1
- l1 = l1.next
- else:
- prev.next = l2
- l2 = l2.next
- prev = prev.next
- prev.next = l1 if l1 is not None else l2
- return prehead.next
- View Code
来源: http://www.bubuko.com/infodetail-3379694.html