Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Find merge point of two linkedlists - solution 1
/* Find merge point of two linkedlists Using Set, Overall time complexity: O(N log N + M log N) Author: Jayesh Chandrapal */ import java.util.*; import java.lang.*; class Rextester { public static void main(String args[]) { // Create two merge linked lists Node node1 = new Node(10); Node node2 = new Node(20); Node node3 = new Node(30); Node node4 = new Node(40); Node node5 = new Node(50); Node node6 = new Node(60); Node list1 = node1; node1.next = node2; node2.next = node3; node3.next = node5; node5.next = node6; Node list2 = node4; node4.next = node3; /* 10 -> 20 -> 30 -> 50 -> 60 40 Merge point : 30 */ // Find and display merge node System.out.println("Merge node: " + findMergePoint(list1, list2)); } /* Returns merge node for given two linked lists. Overall time complexity: O(N log N + M log N) where N = list1 size, M = list2 size. @param: list1 first linked list head node @param: list2 second linked list head node @return Node merge node where two given linked lists merge. Return null if linked lists do not merge. */ public static Node findMergePoint(Node list1, Node list2) { Set<Node> visited = new HashSet<Node>(); Node mergeNode = null; Node current = list1; while(current != null) { // O(N * log N) visited.add(current); current = current.next; } current = list2; while(current != null) { // O(M * log N) if(visited.contains(current)) { mergeNode = current; break; } current = current.next; } return mergeNode; } } class Node { int data; Node next; Node(int data) { this(data, null); } Node(int data, Node next) { this.data = data; this.next = next; } @Override public String toString() { return String.valueOf(data); } }
run
|
edit
|
history
|
help
0
swastik
moneda
Coding Challenge - 03 (Prime numbers)
piglatin
jb12.0 threads.enums
Quadratic_Equation.java
Max in 2D array
continue
updated
j