[剣指Offer]チェーンテーブルで重複するノードを削除(Java)

タイトル
チェーンテーブルの重複するノードを削除する--newcoder剣指Offer 56
 
タイトルの説明
*並べ替えられたチェーンテーブルに重複するノードが存在する場合は、チェーンテーブルの重複するノードを削除します.重複するノードは保持されません.*チェーンテーブルヘッダポインタに戻ります.*例えば、チェーンテーブル1->2->3->3->4->4->5の処理後は1->2->5
 
構想
*1、新しい前駆ノード、nextはpHeadを指し、ヘッドノード要素が重複するシーンを処理しやすい*2、ダブルポインタ、1つのpreポインタは前の重複しないノードを指し、1つのcurは現在遍歴しているノードを指し、状況別処理*3、重複しているノードを遍歴すると、preポインタのnextは現在重複しているノードの最後のノードのnextを指し、すなわち、重複要素を削除し、curポインタを後ろに*4、重複しないノードを遍歴すると、pre、curポインタを同時に後ろに移動するだけでよい
 
コード#コード#

package com.codinginterviews.list;

/**
 *   ：
 *            -- newcoder   Offer 56
 * 
 *     ：
 *          ，       ，            ，        ，
 *        。 
 *   ，  1->2->3->3->4->4->5      1->2->5
 *
 */
public class DeleteDuplication {
	static class ListNode {
		int val;
		ListNode next;
		public ListNode(int val) {
			this.val = val;
		}
		
		//              
        @Override
        public String toString() {
            if (this.next == null) {
                return String.valueOf(this.val);
            }
            return this.val + "->" + this.next.toString();
        }
	}
	
 
	
	/**
	 *   ：
	 *               0->1->1->2  =>   0->2 
	 * 
	 *   ：
	 * 1、         ，           ，    
	 * 2、       
	 */
	public static ListNode deleteDuplication(ListNode pHead) {
		if (pHead == null) {
			return pHead;
		}
		
		//      
		ListNode root = new ListNode(-1);
		root.next = pHead;
		
		//     
		ListNode preNode = root;
		ListNode curNode = pHead;
		
		while (curNode != null && curNode.next != null) {
			//       ，         ，pre->next             next
			if (curNode.val == curNode.next.val) {
				while (curNode != null && curNode.next != null && curNode.val == curNode.next.val) {
					curNode = curNode.next;
				}
				// curNode               
				//       
				preNode.next = curNode.next;
			} else {
				preNode = curNode;
			}
			//   curNode
			curNode = curNode.next;
		}
		
        return root.next;		
	}
	
	/**
	 *   ：
	 * 1、      ，next  pHead，              
	 * 2、   ，  pre             ，  cur         ，     
	 * 3、          ，pre   next                next,       ，cur    
	 * 4、          ，   pre、cur        
	 */
    public static ListNode deleteDuplicationII(ListNode pHead){
        if(pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode root = new ListNode(-1);
        root.next = pHead;
        
        ListNode pre = root;
        ListNode cur = pHead;
        
        while (cur != null) {
            boolean dup = false;
            while (cur.next != null && cur.val == cur.next.val) {
                dup = true;
                cur = cur.next;
            }
            if (dup) {
                pre.next = cur.next;
                cur = cur.next;
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        return root.next; 
    }
	
/**
 * ==========================================================================
 *              ，        
 * ==========================================================================
 * 	
 */
	
	
	/**
	 *   ：
	 * o(n)               ,          
	 * 0->1->1->2  =>   0->1->2 
	 * 
	 *   ：
	 * 1、    ，                     
	 * 2、      (   ，     )
	 * 
	 */
	public static ListNode deleteDuplicationReamainFirstOne(ListNode pHead) {
		if (pHead == null) {
			throw new RuntimeException("link is empty");
		}
		
		ListNode root = new ListNode(-1);
		root.next = pHead;
		
		ListNode pre = root;
		ListNode curNode;
		
		while (pre != null) {
			curNode = pre.next;
			//               
			if (curNode != null && pre.val == curNode.val) {
				pre.next = curNode.next;
			//      pre    
			} else {
				pre = pre.next;
			}
		}
		
		return root.next;
	}
	
	
	/**
	 *   :
	 * o(n)               ,           
	 * 0->1->1->2  =>   0->1->2 
	 * 
	 *   ：
	 * 1、    ，                   
	 * 2、      (   ，     )
	 * 
	 */
	public static ListNode deleteDuplicationRemainLastOne(ListNode head) {
		if (head == null) {
			throw new RuntimeException("link is empty");
		}
		
		ListNode newHead = head;
		
		ListNode preNode = newHead;
		ListNode curNode = newHead.next;
	
		//             ，              
		if (preNode.val == curNode.val) {
			while (preNode.val == curNode.val) {
				preNode = preNode.next;
				curNode = curNode.next;
			}
			newHead = preNode;
		}
		
		//            
		while (curNode != null && curNode.next != null) {
			if (curNode.val != curNode.next.val) {
				preNode = curNode;
			} else {
				preNode.next = curNode.next;
			}
			curNode = curNode.next;
		}
		
		return newHead;
	}
	
    public static void main(String args[]) {
        
		ListNode head = createTestLinkedList(5, new ListNode(4));
        //    
        System.out.println("origin link: " + head);
 
        //       
        System.out.println("remove repeat node: " + deleteDuplicationII(head));
 
        
		ListNode head1 = createTestLinkedList(5, new ListNode(4));
        //       ，          
        System.out.println("remove repeat node but left first one: " + deleteDuplicationReamainFirstOne(head1));
        
        
		ListNode head2 = createTestLinkedList(5, new ListNode(4));
        //       ，           
        System.out.println("remove repeat node but left last one: " + deleteDuplicationRemainLastOne(head2));
        
    }
    
    private static ListNode createTestLinkedList(int n, ListNode addNode) {
        ListNode head = new ListNode(0);
        ListNode head1 = new ListNode(0);
        head.next = head1;
        ListNode curNode = head1;
        int count = 1;
        for (int i = 1; i < n; i++) {
            curNode.next = new ListNode(i);
            curNode = curNode.next;
            if (i == 2 && count >= 0) {
            	i--;
            	count--;
            }
        }
        curNode.next = addNode;
        return head;
    }
 
}