CareerCup

Iterate through both lists and insert each node of each list in a hash table or a balanced binary search tree indexed by (name, phone) key-value pairs (in C++ you can use a set<pair<string, string>>, assuming name and phone are strings). When inserting, if an element is already there, then just ignore the current node and do not insert it.

Then iterate through the set / hash table, building a new list along the way. Each node retrieved from the set is a new node in the linked list.

Time complexity: linear in the size of the lists
Space complexity: linear in the size of the lists

Other possible approaches include sorting both lists to avoid using additional space, but it comes at the cost of raising running time to O(n log(n)); OR you can use nested loops to check if each node exists in the other list or on the rest of the current list, but that would be n^2.

public class Node implements Comparable<Node>
{
private String name;
private int phoneNo;
private String address;

public int compareTo(Node n)
{
if(n==null || !n instanceOf Node)
{
return -1;
}
if(name.equals(n.name)&&phoneNo.equals(n.phoneNo))
{
return 0;
}
return -1;
}
}

public class ListService
{
	public static Node mergeWithoutDuplicates(Node l1,Node l2) throws NullPointerException
	{
		if(l1==null||l2==null)
		{
			throw new NullPointerException();
		}
		Node p=l1;
		while(p.next!=null)
		{
			p=p.next;
			
		}
		p.next=l2;
		return(removeDuplicates(l1));
	}
	
	private Node removeDuplicates(Node ls)
	{
		HashMap<Node,Boolean> mp=new HashMap<Node,Boolean>();
		Node s=null;
		Node f=ls;
		while(f!=null)
		{
			if(!mp.containsKey(f))
			{
				mp.put(f,true);
			}else
			{
				s.next=f.next;
				f.next=null;
				f=s.next;
			}
		}
		return ls;
	}
}

//O(n+m) space and O(n+m) time.

geeksforgeeks.org dynamic-programming-set-34-assembly-line-scheduling

geeksforgeeks dynamic-programming-set-34-assembly-line-scheduling

dana,
can the original lists be modified ?

This is a O(n2) complexity solution, but does not require extra space. The 2 input linked lists are inputted as an array 'list'.

for (int j = 0; j < list.Length; j++)
{
	var node = list[j];
	while (node != null)
	{
		var left = head;
		while (left != curpos)
		{
			if (node.Value == left.Value)
			{
				break;
			}

			left = left.Next;
		}

		if (left == curpos && left.Value != node.Value)
		{
			curpos.Next = node;
			curpos = curpos.Next;
		}

		node = node.Next;
	}
}
curpos.Next = null;
return head;