fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class CCLinkedList{
  8. 	public static void main(String[] args){
  9.  
  10. 		// LinkedListExample ex=new LinkedListExample();
  11. 		// ex.insert(3);
  12. 		// ex.insert(5);
  13. 		// ex.insert(8);
  14. 		// ex.insert(5);
  15. 		// ex.insert(10);
  16. 		// ex.insert(2);
  17. 		// ex.insert(1);
  18.  
  19. 		/*
  20. 		* CC2_1
  21. 		*/
  22. 		// ex.traverse();
  23. 		// System.out.println("==");
  24. 		// ex.removeDups();
  25. 		// ex.traverse();
  26. 		// System.out.println("==");
  27. 		// ex.removeDupsWithoutBuffer();
  28. 		// ex.traverse();
  29.  
  30.  
  31. 		/*
  32. 		* CC2_2
  33. 		*/
  34. 		// ex.traverse();
  35. 		// System.out.println("==");
  36. 		// Node n=ex.findKthToLast(5);
  37. 		// System.out.println(n.value);
  38.  
  39.  
  40. 		// ex.traverse();
  41. 		// System.out.println("==");
  42. 		// Node k=ex.partition(5);
  43. 		// while(k.next!=null){
  44. 		// 	System.out.println(k.value);
  45. 		// 	k=k.next;
  46. 		// }
  47. 		// System.out.println(k.value);
  48.  
  49.  
  50. 		LinkedListExample ex1=new LinkedListExample();
  51. 		ex1.insert(1);
  52. 		ex1.insert(2);
  53. 		ex1.insert(3);
  54. 		ex1.insert(4);
  55. 		ex1.insert(5);
  56. 		ex1.insert(6);
  57. 		ex1.insert(7);
  58. 		ex1.insert(8);
  59. 		LinkedListExample ex2=new LinkedListExample();
  60. 		ex2.insert(8);
  61.  
  62. 		// 1->2->3->4->5->6->7->8;
  63. 		//          ^           |
  64. 		//          |___________|
  65. 		ex1.createCorruptCircular(ex1.head, 4);
  66.  
  67. 		System.out.println("isCorruptedCircular: "+ex1.findLoopDetection(ex1.head));
  68.  
  69. 		Node n=ex1.findLoopDetectionNode(ex1.head);
  70. 		System.out.println("LoopStartingNode: "+n.value);
  71.  
  72.  
  73. 		// ex1.makeIntersection(ex1.head,ex2.head, 4);
  74. 		// Node n=ex1.findIntersection(ex1.head,ex2.head);
  75. 		// System.out.println("Intersection node: "+n.value);
  76. 		// ex2.insert(8);
  77.  
  78.  
  79. 		// Node n=ex2.sumList(ex1.head,ex2.head,0); //backward
  80. 		// while(n!=null){
  81. 		// 	System.out.println(n.value);
  82. 		// 	n=n.next;
  83. 		// }
  84.  
  85.  
  86. 		// Node n=ex2.padding(ex1.head,ex2.head); // forward, padding needed
  87. 		// while(n!=null){
  88. 		// 	System.out.println(n.value);
  89. 		// 	n=n.next;
  90. 		// }
  91.  
  92. 		// System.out.println(ex1.isPalindrome(ex1.head));
  93.  
  94.  
  95. 	}
  96.  
  97.  
  98. }
  99.  
  100. class Node<Integer>{
  101. 	protected Node<Integer> next;
  102. 	protected int value;
  103.  
  104. 	public Node(int value){
  105. 		this.value=value;
  106. 	}
  107. }
  108.  
  109. class LinkedListExample{
  110.  
  111. 	public Node head;
  112.  
  113. 	public Node findLoopDetectionNode(Node n){
  114.  
  115. 		if(n==null) return null;
  116.  
  117. 		Node slow=n;
  118. 		Node fast=n;
  119.  
  120. 		while(fast!=null&&fast.next!=null){
  121. 			slow=slow.next;
  122. 			fast=fast.next.next;
  123. 			if(slow==fast) break;
  124. 		}
  125. 		if(fast==null || fast.next==null) return null;
  126.  
  127. 		slow=n;
  128. 		while(slow!=fast){
  129. 			slow=slow.next;
  130. 			fast=fast.next;
  131. 		}
  132.  
  133. 		return slow;
  134.  
  135. 	}
  136.  
  137. 	public boolean findLoopDetection(Node n){
  138.  
  139. 		if(n==null) return false;
  140.  
  141. 		Node slow=n;
  142. 		Node fast=slow;
  143.  
  144.  
  145. 		while(fast!=null&&fast.next!=null){
  146. 			slow=slow.next;
  147. 			fast=fast.next.next;
  148. 			if(slow==fast) break;
  149. 		}
  150. 		if(fast==null || fast.next==null) return false;
  151.  
  152. 		return true;
  153.  
  154. 	}
  155.  
  156. 	public void createCorruptCircular(Node n,int count){
  157.  
  158. 		Node tempN=n;
  159. 		Node tail=getTailNode(tempN);
  160.  
  161. 		while(n!=null){
  162. 			if(count==1){
  163. 				tail.next=n;
  164. 				return;
  165. 			}
  166. 			count--;
  167. 			n=n.next;
  168. 		}
  169.  
  170. 	}
  171.  
  172. 	public Node getTailNode(Node n){
  173. 		while(n.next!=null){
  174. 			n=n.next;
  175. 		}
  176. 		return n;
  177. 	}
  178.  
  179.  
  180. 	public Node findIntersection(Node n1,Node n2){
  181.  
  182. 		if(n1==null || n2==null) return null;
  183.  
  184. 		//If intersected, two must have the same tail
  185. 		//tail insepection
  186. 		if(!sameTail(n1, n2)) return null; // have different tale
  187.  
  188. 		//we compare the size, to make the same staring position
  189. 		int sizeN1=sizeCheck(n1);
  190. 		int sizeN2=sizeCheck(n2);
  191. 		int sizeDiff=Math.abs(sizeN1-sizeN2);
  192.  
  193. 		Node longer= sizeN1>=sizeN2 ? n1:n2;
  194. 		Node shorter= sizeN1>=sizeN2 ? n2:n1;
  195.  
  196. 		//we get kth node to make the same starting point between longer and shorter
  197. 		if(sizeDiff>0) longer = getKthNode(longer, sizeDiff);
  198.  
  199. 		//Now we get the same starting point
  200. 		//move until positioned in the same node
  201. 		while(longer!=shorter){
  202. 			longer=longer.next;
  203. 			shorter=shorter.next;
  204. 		}
  205.  
  206. 		return longer;
  207. 	}
  208.  
  209. 	public Node getKthNode(Node n, int count){
  210. 		while(count>0){
  211. 			n=n.next;
  212. 			count--;
  213. 		}
  214. 		return n;
  215. 	}
  216.  
  217.  
  218. 	public int sizeCheck(Node n){
  219. 		Node tempN=n;
  220. 		int size=0;
  221. 		while(tempN!=null){
  222. 			size++;
  223. 			tempN=tempN.next;
  224. 		}
  225. 		return size;
  226. 	}
  227.  
  228. 	public boolean sameTail(Node n1, Node n2){
  229.  
  230. 		Node tempN1=n1;
  231. 		Node tempN2=n2;
  232.  
  233. 		int tailValueN1=0;
  234. 		int tailValueN2=0;
  235.  
  236. 		while(tempN1!=null){
  237. 			tailValueN1=tempN1.value;
  238. 			tempN1=tempN1.next;
  239. 		}
  240. 		while(tempN2!=null){
  241. 			tailValueN2=tempN2.value;
  242. 			tempN2=tempN2.next;
  243. 		}
  244.  
  245. 		return tailValueN1==tailValueN2?true:false;
  246.  
  247. 	}
  248.  
  249. 	public void makeIntersection(Node n1, Node n2, int value){
  250.  
  251. 		while(n2.next!=null){
  252. 			n2=n2.next;
  253. 		}
  254.  
  255. 		while(n1!=null){
  256. 			if(n1.value==value){
  257. 				n2.next=n1;
  258. 				return;
  259. 			}
  260. 			n1=n1.next;
  261. 		}
  262. 	}
  263.  
  264. 	/*
  265. 	* CC2_6
  266. 	*/
  267. 	public boolean isPalindrome(Node n){
  268.  
  269. 		Node fast=n; // skip two elements
  270. 		Node slow=n;
  271.  
  272. 		Stack<Integer> stack=new Stack<Integer>(); // Important
  273.  
  274. 		// when fast=null, slow=N/2
  275. 		while(fast!=null && fast.next!=null){ // Important
  276. 			stack.push(slow.value);
  277. 			slow=slow.next;
  278. 			fast=fast.next.next;
  279. 		}
  280.  
  281. 		//if odd number fast != null
  282. 		//if even fast == null
  283. 		if(fast!=null){ 
  284. 			slow=slow.next;
  285. 		}
  286.  
  287. 		while(slow!=null){
  288. 			int compare=stack.pop();
  289. 			if(compare!=slow.value)
  290. 				return false;
  291. 			slow=slow.next;
  292. 		}
  293. 		return true;
  294. 	}
  295.  
  296.  
  297. 	public void insert(int value){
  298.  
  299. 		if(head==null){
  300. 			head = new Node(value);
  301. 		}else{
  302. 			insertNode(head, value);
  303. 		}
  304. 	}
  305.  
  306.  
  307. 	/*
  308. 	* CC2_5_follow_up
  309. 	*/
  310. 	public Node padding(Node n1, Node n2){
  311.  
  312. 		//first find the size of likedlist
  313. 		int sizeN1=0;
  314. 		Node tempN1=n1; // IMPORTANT create temp node and move, because we pass n1, n2 head to other functions
  315. 		while(tempN1!=null){
  316. 			sizeN1++;
  317. 			tempN1=tempN1.next;
  318. 		}
  319.  
  320. 		int sizeN2=0;
  321. 		Node tempN2=n2;
  322. 		while(tempN2!=null){
  323. 			sizeN2++;
  324. 			tempN2=tempN2.next;
  325. 		}
  326.  
  327. 		if(sizeN1>sizeN2){
  328. 			n2=addZero(n2,(sizeN1-sizeN2));
  329. 		}else if(sizeN1<sizeN2){
  330. 			n1=addZero(n1,(sizeN2-sizeN1));
  331. 		}
  332.  
  333. 		Node currN=sumList2(n1,n2);
  334. 		return currN;
  335. 	}
  336.  
  337. 	public Node addZero(Node n, int count){
  338. 		while(count>0){
  339. 			n=insertHead(n, 0);
  340. 			count--;
  341. 		}
  342. 		return n;
  343. 	}
  344.  
  345. 	public Node insertHead(Node n,int value){
  346. 		Node newNode=new Node(value);
  347. 		newNode.next=n;
  348. 		return newNode;
  349. 	}
  350.  
  351. 	public Node sumList2(Node n1, Node n2){
  352.  
  353. 		// 6->1->7
  354. 		// 2->9->5
  355. 		// =======
  356. 		// 6+2=8, save 8
  357. 		// 1+9=10, save 10
  358. 		// 7+5=12, save 12
  359. 		// when linking to each node, we examine if the value >=10, if so, update the previous node value+1;
  360.  
  361. 		// Consider all parameters are null
  362. 		if(n1==null && n2==null) return null;
  363.  
  364. 		int result=0;
  365. 		if(n1!=null){
  366. 			result += n1.value;
  367. 		}
  368.  
  369. 		if(n2!=null){
  370. 			result += n2.value;
  371. 		}
  372.  
  373.  
  374. 		Node currNode=new Node(result);
  375. 		if(n1.next!=null || n2.next!=null){
  376. 			Node nextNode = sumList2(n1.next==null?null:n1.next,n2.next==null?null:n2.next);
  377. 			//nextNode examinization before attached.
  378. 			if(nextNode.value>=10){
  379. 				nextNode.value=(nextNode.value%10);
  380. 				currNode.value=currNode.value+1;
  381. 			}
  382. 			currNode.next=nextNode;
  383. 		}
  384.  
  385. 		return currNode;
  386.  
  387.  
  388. 	}
  389.  
  390.  
  391.  
  392. 	/*
  393. 	* CC2_5
  394. 	*/
  395. 	public Node sumList(Node n1, Node n2, int carry){
  396.  
  397. 		// 7->1->6
  398. 		// 5->9->2
  399. 		// =======
  400. 		// 7+5=12, take only second digit 2 and pass the carry to next recursive
  401. 		// 1+9+1(carry), take only 1, pass 1 carry to next
  402. 		// 6+2+1(carry), take 9
  403. 		// return head node 2 that linked to 1 -> 9
  404.  
  405. 		// Consider all parameters are null
  406. 		if(n1==null && n2==null && carry==0) return null;
  407.  
  408. 		int result=0;
  409. 		if(n1!=null){
  410. 			result += n1.value;
  411. 		}
  412.  
  413. 		if(n2!=null){
  414. 			result += n2.value;
  415. 		}
  416.  
  417. 		// add carry if exists
  418. 		result += carry;
  419.  
  420. 		// get next carry
  421. 		int nextCarry=result>=10?1:0;
  422.  
  423. 		// we only take second digit
  424. 		result=result%10;
  425.  
  426. 		Node currNode=new Node(result);
  427.  
  428. 		Node nextNode = sumList(n1.next==null?null:n1.next,n2.next==null?null:n2.next,nextCarry);
  429. 		currNode.next=nextNode;
  430.  
  431. 		return currNode;
  432.  
  433.  
  434.  
  435.  
  436. 	}
  437.  
  438.  
  439.  
  440.  
  441. 	public void insertNode(Node n,int value){
  442. 		while(n.next!=null){
  443. 			n=n.next;
  444. 		}
  445. 		n.next=new Node(value);
  446. 	}
  447.  
  448. 	public void traverse(){
  449. 		Node temp=head;
  450. 		while(temp!=null){
  451. 			System.out.println(temp.value);
  452. 			temp=temp.next;
  453. 		}
  454.  
  455. 	}
  456.  
  457. 	public Node findKthToLast(int k){
  458.  
  459. 		//O(N^2)
  460. 		//if we use two loop using runner together
  461. 		//inside inner loop, count the number of remaining elements to the end
  462. 		//if the number == k, return the current Node
  463.  
  464. 		//O(N)
  465. 		//use two pointers
  466. 		//one pointer moves until i<k
  467. 		//then move two pointer together
  468. 		//When p1 hits the null, the location of p2 is the kth
  469.  
  470. 		Node n1 = head;
  471. 		Node n2 = head;
  472. 		for(int i=0;i<k;i++){ // Important
  473. 			if(n1.next!=null){
  474. 				n1=n1.next;
  475. 			}else{
  476. 				return null; // k is larger than the list length
  477. 			}
  478. 		}
  479. 		while(n1.next!=null){
  480. 			n1=n1.next;
  481. 			n2=n2.next;
  482. 		}
  483. 		return n2;
  484.  
  485. 	}
  486.  
  487.  
  488.  
  489. 	// O(N^2)
  490. 	public void removeDupsWithoutBuffer(){
  491. 		// run two loops
  492. 		Node current=head;
  493. 		while(current.next !=null){
  494. 			int value=current.value;
  495. 			Node runner=current.next;
  496. 			Node prevRunner=null;
  497. 			while(runner.next != null){
  498. 				if(runner.value==value){
  499. 					prevRunner.next=runner.next; // Memorize it, Important			
  500. 				}else{
  501. 					prevRunner=runner; // Memorize it, Important
  502. 				}
  503. 				runner=runner.next;
  504. 			}
  505. 			current=current.next;
  506. 		}
  507.  
  508.  
  509. 	}
  510.  
  511.  
  512.  
  513. 	public void removeDups(){
  514.  
  515. 		HashSet<Integer> hash = new HashSet<Integer>();
  516. 		Node n=head;
  517.  
  518. 		Node prev=null; // to remove node, need to save the prev node
  519. 		while(n.next!=null){
  520. 			if(hash.contains(n.value)){
  521. 				prev.next=n.next; //previous node jumps to the current.next node, so the current node deleted
  522. 			}else{
  523. 				hash.add(n.value); //HashSet only contains not-duplicated data
  524. 				prev=n;
  525. 			}
  526. 			n=n.next;
  527. 		}
  528. 	}
  529.  
  530.  
  531. 	/*
  532. 	* CC2_4
  533. 	*/	
  534. 	public Node partition(int pValue){
  535.  
  536. 		Node n=head;
  537.  
  538. 		Node leftStart=null;
  539. 		Node leftEnd=null;
  540. 		Node rightStart=null;
  541. 		Node rightEnd=null;
  542.  
  543. 		while(n!=null){ // listen carefully, loop to the end node
  544.  
  545. 			Node next=n.next; // create new one that indicates the next node for the next loop
  546. 			n.next=null; // we save current Node to the list, make current node's next to blank
  547.  
  548. 			if(n.value<pValue){
  549. 				// update left Linked list
  550. 				if(leftStart==null){
  551. 					leftStart=n;
  552. 					leftEnd=leftStart;
  553. 				}else{
  554. 					leftEnd.next=n;
  555. 					leftEnd=n;
  556. 				}
  557. 			}else{
  558. 				// update right Linked List
  559. 				if(rightStart==null){
  560. 					rightStart=n;
  561. 					rightEnd=rightStart;
  562. 				}else{
  563. 					rightEnd.next=n;
  564. 					rightEnd=n;
  565. 				}
  566. 			}
  567. 			n=next; //return next, NOT n.next
  568.  
  569. 		}
  570.  
  571. 		//Merge two links
  572. 		leftEnd.next=rightStart;
  573. 		return leftStart;
  574.  
  575.  
  576. 	}
  577.  
  578.  
  579. 	/*
  580. 	* CC2_3
  581. 	*/
  582. 	public boolean removeNode(Node n){
  583.  
  584. 		if(n==null||n.next==null) return false;
  585.  
  586. 		//IMPORTANT
  587. 		//copy next node data to curret node
  588. 		//then, link to next.next
  589. 		Node nextNode=n.next;
  590. 		n.value=nextNode.value;
  591. 		n.next=nextNode.next;
  592. 		return true;
  593.  
  594. 	}
  595.  
  596.  
  597. 	public void removeNodeIfValueMatched(int value){
  598. 		Node temp=head;
  599. 		while(temp.next!=null){
  600.  
  601. 			// in this case, we do not need prevNode, directly, compare next node from current
  602. 			if(temp.next.value==value){
  603. 				temp.next=temp.next.next;
  604. 				System.out.println("removed: "+value);
  605. 			}
  606. 			temp=temp.next;
  607. 		}
  608. 	}
  609.  
  610.  
  611. }
Success #stdin #stdout 0.09s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
isCorruptedCircular: true
LoopStartingNode: 4
https://ideone.com/UEoz7A
CC_2_LinkedList
language:
Java (HotSpot 12)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!