2014年5月10日星期六

Loop Solution with Backtracking - Remove Duplicates from Sorted List II

The idea below is to loop the list, if the node satisfy two conditions: node.val != node.next.val (next not null) && node.val != preValue, then add it to new result list, otherwise(both case no matter satisfy or not) update node, and preValue.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = new ListNode(Integer.MIN_VALUE);
        ListNode newNode = newHead;
        int preValue = newHead.val;
        ListNode node = head;
        while(node.next != null){
            ListNode next = node.next;
            if(node.val != node.next.val){
                if(node.val != preValue){
                    newNode.next = node;
                    node.next = null;
                    newNode = node;
                }
            }
            preValue = node.val;
            node = next;
        }
        if(node != null && node.val != preValue){
            newNode.next = node;
        }
        return newHead.next;
        // ListNode newHead = new ListNode(Integer.MIN_VALUE);
        // newHead.next = head;
        // ListNode befDup = newHead;
        // ListNode dupStart = head;
        // ListNode dupLoop = dupStart.next;
        // ListNode curDup = new ListNode(Integer.MIN_VALUE);;
        // while(dupLoop != null){
        //     if(dupStart.val != dupLoop.val && dupStart.val != curDup.val){
        //         befDup = dupStart;
        //         dupStart = dupLoop;
        //         dupLoop = dupLoop.next;
        //     }else if(dupStart.val != dupLoop.val && dupStart.val == curDup.val){
        //         befDup.next = dupStart.next;
        //         dupStart.next = null;
        //         dupStart = dupLoop;
        //         dupLoop = dupLoop.next;
        //     }else if(dupStart.val == dupLoop.val){
        //         curDup.val = dupStart.val;
        //         dupStart.next = dupLoop.next;
        //         dupLoop.next = null;
        //         dupLoop = dupStart.next;
        //     }
        // }
        // if(curDup.val == dupStart.val){
        //     befDup.next = null;
        // }
        // return newHead.next;
    }
}

没有评论: