LearnFrenzy
Sign in Take a free test

Data Structures in Java · Data Structures in Java Programs · Question 3

Merge two sorted linked lists and remove duplicates Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 3 Back to Exercise

Merge two sorted singly linked lists into one sorted list by relinking nodes (no new nodes), then remove duplicate values in place.

Solution
Main.java
public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }

    static Node of(int... vals) {
        Node dummy = new Node(0, null), tail = dummy;
        for (int v : vals) { tail.next = new Node(v, null); tail = tail.next; }
        return dummy.next;
    }

    static String str(Node n) {
        StringBuilder sb = new StringBuilder("[");
        for (; n != null; n = n.next) sb.append(n.val).append(n.next != null ? ", " : "");
        return sb.append(']').toString();
    }

    static Node merge(Node a, Node b) {
        Node dummy = new Node(0, null), tail = dummy;      // dummy head: no special case for the first node
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;                   // append whatever is left
        return dummy.next;
    }

    static Node dedupe(Node head) {
        for (Node cur = head; cur != null && cur.next != null; ) {
            if (cur.val == cur.next.val) cur.next = cur.next.next;   // skip the duplicate
            else cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) {
        Node a = of(1, 4, 7, 9), b = of(2, 4, 5, 9, 12);
        System.out.println(str(a) + " + " + str(b));
        Node m = merge(a, b);
        System.out.println("merged:  " + str(m));
        System.out.println("deduped: " + str(dedupe(m)));
    }
}

Output Verified by compiling and running

[1, 4, 7, 9] + [2, 4, 5, 9, 12]
merged:  [1, 2, 4, 4, 5, 7, 9, 9, 12]
deduped: [1, 2, 4, 5, 7, 9, 12]

Merging takes O(n + m) time and O(1) extra space because it only rewires next pointers. In a sorted list duplicates are adjacent, so one pass removes them.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links