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
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)));
}
}
[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!