fork(3) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Node
  6. {
  7. 	int data;
  8. 	Node next;
  9.  
  10. 	Node(int data){
  11. 		this.data = data;
  12. 		next = null;
  13. 	}
  14.  
  15. 	void append(Node head, int val){
  16. 		Node temp = new Node(val);
  17. 		Node cur = head;
  18.  
  19. 		if(head == null)
  20. 		{
  21. 			return;
  22. 		}
  23. 		while(cur.next != null)
  24. 		{
  25. 			cur = cur.next;
  26. 		}
  27. 		cur.next = temp;
  28. 		return;
  29.  
  30. 	}
  31.  
  32. 	void display(){
  33.  
  34. 		Node cur = this;
  35. 		while(cur != null)
  36. 		{
  37. 			System.out.print(cur.data + "->");
  38. 			cur = cur.next;
  39. 		}
  40. 	}
  41. }
  42.  
  43. class Ideone
  44. {
  45. 	public Node findMiddle(Node head){
  46. 		if(head == null )
  47. 			return null;
  48.  
  49. 		Node slow, fast;
  50. 		slow = head;
  51. 		fast = head;
  52.  
  53. 		while(fast != null && fast.next != null && fast.next.next != null){
  54. 			slow = slow.next;
  55. 			fast = fast.next.next;
  56. 		}
  57. 		return slow;
  58.  
  59. 	}
  60.  
  61.  	public Node merge(Node first, Node second){
  62.  
  63.  		Node head = null;
  64.  		while(first != null && second != null){
  65.  
  66.  			if(first.data < second.data){
  67.  				if(head == null){
  68.  					head = new Node(first.data);
  69.  				}
  70.  				else
  71.  					head.append(head,first.data);
  72.  				first = first.next;
  73.  			}
  74.  			else if(second.data < first.data){
  75.  					if(head == null){
  76.  					head = new Node(second.data);
  77.  				}
  78.  				else
  79.  					head.append(head,second.data);
  80.  				second = second.next;
  81.  			}
  82.  			else{
  83.  					if(head == null){
  84.  						head = new Node(first.data);
  85.  						head.append(head,second.data);
  86.  					}
  87.  					else{
  88.  						head.append(head,first.data);
  89.  						head.append(head,second.data);
  90.  					}
  91.  				second = second.next;
  92.  				first = first.next;
  93.  			}
  94.  		}	
  95.  			while(first != null){
  96.  				if(head == null){
  97.  					head = new Node(first.data);
  98.  				}
  99.  				else
  100.  					head.append(head,first.data);
  101.  				first = first.next;
  102.  			}
  103.  
  104.  				while(first != null){
  105.  				if(head == null){
  106.  					head = new Node(first.data);
  107.  				}
  108.  				else
  109.  					head.append(head,first.data);
  110.  				first = first.next;
  111.  				}
  112.  
  113.  				while(second != null){
  114.  				if(head == null){
  115.  					head = new Node(second.data);
  116.  				}
  117.  				else
  118.  					head.append(head,second.data);
  119.  				second = second.next;
  120.  			}
  121.  
  122.  
  123.  		return head;	
  124.  	}
  125.  
  126. 	public Node mergeSort(Node head){
  127.  
  128. 		if(head == null)
  129. 			return null;
  130.  
  131. 		if(head.next == null)
  132. 			return head;
  133.  
  134. 		Node first = head;
  135. 		Node mid = findMiddle(first);
  136. 		Node second = mid.next;
  137. 		mid.next = null;
  138. 		Node left = mergeSort(first);
  139. 		Node right = mergeSort(second);
  140. 		Node result = merge(left, right);
  141. 		return result;
  142.  
  143. 	}
  144.  
  145. 	public static void main (String[] args) throws java.lang.Exception
  146. 	{
  147. 		Node head = new Node(5);
  148. 		head.append(head,1);
  149. 		head.append(head,5);
  150. 		head.append(head,1);
  151. 		head.append(head,5);
  152. 		head.append(head,3);
  153.  		System.out.println("Unsoreted linked list:");
  154. 		head.display();
  155. 		Ideone tmp = new Ideone();
  156. 		Node result = tmp.mergeSort(head);
  157. 		System.out.println("\nSorted linked list:");
  158.  		result.display();
  159. 	}
  160. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Unsoreted linked list:
5->1->5->1->5->3->
Sorted linked list:
1->1->3->5->5->5->
https://ideone.com/4WVYHc
Merge sort for linked list
language:
Java (HotSpot 12)
created:
11 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!