데이터 구조: 링크 면접 문제

package com.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {
	public static void main(String[] args){
		//     
		HeroNode h1 = new HeroNode(1, "  ", "   ");
		HeroNode h2 = new HeroNode(3, "  ", "   ");
		HeroNode h3 = new HeroNode(5, "  ", "  ");
		HeroNode h4 = new HeroNode(7, "  ", "   ");
		
		SingleLinkedList list = new SingleLinkedList();
		//            
//		list.add(h1);
//		list.add(h2);
//		list.add(h3);
//		list.add(h4);
		
		//         
		list.addByOrder(h1);
		list.addByOrder(h4);
		list.addByOrder(h3);
		list.addByOrder(h2);
		System.out.println("              ...");
		list.list();
		
//		//     
//		HeroNode newHeroNode = new HeroNode(2, "   ", "   ");
//		list.update(newHeroNode);
//		System.out.println("        ...");
//		list.list();
//		
//		//     
//		list.del(2);
//		list.del(1);
//		System.out.println("        ...");
//		list.list();
		
		System.out.println("   4   :");
		HeroNode cur = findLastIndexNode(list.getHeroNode(), 4);
		System.out.println(cur);
		System.out.println("       :"+getLength(list.getHeroNode()));
		
		System.out.println("    ....");
		reversePrint(list.getHeroNode());
		
		System.out.println("list2....");
		SingleLinkedList list2 = new SingleLinkedList();
		//     
		HeroNode h5 = new HeroNode(2, "   ", "   ");
		HeroNode h6 = new HeroNode(4, "   ", "   ");
		HeroNode h7 = new HeroNode(6, "  ", "   ");
		HeroNode h8 = new HeroNode(8, "   ", "  ");
		list2.addByOrder(h8);
		list2.addByOrder(h6);
		list2.addByOrder(h5);
		list2.addByOrder(h7);
		list2.list();
		
		System.out.println("  ...");
		HeroNode merge = mergeList(list.getHeroNode(),list2.getHeroNode());
		
		System.out.println("      ....");
		reverseList(list.getHeroNode());
		list.list();
	}

	//    :           
	public static HeroNode mergeList(HeroNode head1, HeroNode head2){
		HeroNode merge = new HeroNode(0, "", "");
		if(head1.next == null || head2.next == null){
			return null;
		}
		
		HeroNode temp1 = head1.next;
		HeroNode temp2 = head2.next;
		HeroNode temp3 = merge;
		while(temp1 != null && temp2 != null){
			if(temp1.no > temp2.no){
				temp3.next = temp2;
				temp2 = temp2.next;
			}else{
				temp3.next = temp1;
				temp1 = temp1.next;
			}
			temp3 = temp3.next;
		}
		
		if(temp1 != null){
			temp3.next = temp1;
		}
		
		if(temp2 != null){
			temp3.next = temp2;
		}
		
		//      ,   ,             
		HeroNode temp = merge.next;
		while(true){
			//          
			if(temp == null){
				break;
			}
			//       
			System.out.println(temp);
			temp = temp.next; // temp  ,       
		}
				
		return merge;
	}
	
	//    :       
	//            ,            ,             ,           
	public static void reversePrint(HeroNode head){
		if(head.next == null)
			return;	//    ,    
		
		//      ，        
		Stack stack = new Stack();
		HeroNode cur = head.next;
		//            
		while(cur != null){
			stack.push(cur);
			cur = cur.next; // cur  ,            
		}
		//         ,   
		while(stack.size()>0){
			System.out.println(stack.pop());
		}
	}
	
	/**
	 *    :       
	 */
	public static void reverseList(HeroNode head){
		//         ,        ,    ,    
		if(head.next == null || head.next.next == null)
			return;
		
		//         ,           
		HeroNode cur = head.next;
		HeroNode next = null; //             
		HeroNode reverseHead = new HeroNode(0, "", "");
		//        ,        ，     ，       reverseHead    
		while(cur != null){
			next = cur.next; //               
			cur.next = reverseHead.next; //  cur                
			reverseHead.next = cur; //  cur        
			cur = next;//  cur  
		}
		
		//  head.next  reverseHead next,        
		head.next = reverseHead.next;
	}
	
	/**
	 *    :           k   
	 *  @param head       
	 *  @param index    index   
	 *  @return      ,     .     null
	 */
	public static HeroNode findLastIndexNode(HeroNode head, int index){
		if(head.next == null)
				return null; //     
		
		//             
		int size = getLength(head);
		
		//       size-index  ,        k   
		//     index   
		if(index<=0 || index>size){
			return null;
		}
		//         
		HeroNode cur = head.next;
		for(int i=0;i heroNode.no){
				break;
			}else if(temp.next.no == heroNode.no){
				flag = true; //         
				break;
			}
			
			temp = temp.next;
		}
		
		//   flag  
		if(flag){ //     ,      
			System.out.printf("          %d    ,    
",heroNode.no);
		}else{
			//       
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	
	//     (  )
	public void list(){
		//         
		if(head.next == null){
			System.out.println("        ...");
			return;
		}
		//      ,   ,             
		HeroNode temp = head.next;
		while(true){
			//          
			if(temp == null){
				break;
			}
			//       
			System.out.println(temp);
			temp = temp.next; // temp  ,       
		}
	}
}

//   HearNode,  HearNode        
class HeroNode{
	public int no;
	public String name;
	public String nickname;
	public HeroNode next;
	
	public HeroNode(int no, String name, String nickname){
		this.no = no;
		this.name = name;
		this.nickname = nickname;
	}

	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickname="
				+ nickname + "]";
	}
	
	
}