Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LeetCode URL: https://leetcode.com/problems/add-two-numbers/
- // Definition for singly-linked list.
- class ListNode {
- int val;
- ListNode next;
- ListNode(int x) {
- val = x;
- }
- }
- /**
- * Iterative Solution
- *
- * Time Complexity: O(min(M, N))
- *
- * Space Complexity: O(1)
- *
- * M = Length of the input list l1. N = Length of the input list l2.
- */
- class Solution1 {
- public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
- if (l1 == null) {
- return l2;
- }
- if (l2 == null) {
- return l1;
- }
- ListNode dummyHead = new ListNode(-1);
- ListNode prevNode = dummyHead;
- ListNode p = l1;
- ListNode q = l2;
- while (p != null && q != null) {
- if (p.val <= q.val) {
- prevNode.next = p;
- p = p.next;
- } else {
- prevNode.next = q;
- q = q.next;
- }
- prevNode = prevNode.next;
- prevNode.next = null;
- }
- prevNode.next = p == null ? q : p;
- return dummyHead.next;
- }
- }
- /**
- * Recursive Solution
- *
- * Time Complexity: O(min(M, N))
- *
- * Space Complexity: O(min(M, N))
- *
- * M = Length of the input list l1. N = Length of the input list l2.
- */
- class Solution2 {
- public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
- if (l1 == null) {
- return l2;
- }
- if (l2 == null) {
- return l1;
- }
- return mergeTwoListsHelper(l1, l2);
- }
- private ListNode mergeTwoListsHelper(ListNode p, ListNode q) {
- if (p == null) {
- return q;
- }
- if (q == null) {
- return p;
- }
- if (p.val <= q.val) {
- p.next = mergeTwoListsHelper(p.next, q);
- return p;
- } else {
- q.next = mergeTwoLists(p, q.next);
- return q;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement