如何从无序链表中移除重复项--Java版

题目描述：
给定一个没有排序的链表，去掉其重复项，并保留原顺序，如链表1->3->1->5->5->7，去掉重复项变为1->3->5->7。

方法一：顺序删除

思路： 通过双重循环直接在链表上执行删除操作。外层循环用一个指针从第一个节点开始遍历整个链表，然后内层循环用另一个指针遍历其余节点，将与外层循环遍历到的指针所指节点的数据域相同的节点删除（删除的是内层循环的节点）。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
    	//排除空表和单节点情况
        if (head == null || head.next == null) {
            return head;
        }
        ListNode outerCur = head;//用于外层循环，指向链表第一个节点
        ListNode innerCur = null;//内层循环用来遍历outerCur后面的节点
        //一旦涉及节点删除，那么就要找到该节点的前驱节点
        ListNode innerPre = null;//innerCur的前驱节点
        for (; outerCur != null; outerCur = outerCur.next) {
            for (innerCur = outerCur.next, innerPre = outerCur; innerCur != null; ) {
                //找到重复的节点并删除
                if (outerCur.val == innerCur.val) {
                    innerPre.next = innerCur.next;
                    innerCur = innerCur.next;
                } else {
                    innerPre = innerCur;
                    innerCur = innerCur.next;
                }
            }
        }
        return head;
    }
}

算法性能分析： 由于这种方法采用双重循环对链表进行遍历，因此，时间复杂度为O(N^2)。其中，N为链表的长度。在遍历链表的过程中，使用了常量个额外的指针变量来保存当前遍历的节点、前驱节点和被删除的节点，因此，空间复杂度为O(1)。

方法二：递归法

思路： 对于节点cur，首先递归的删除以cur.next为首的子链表中重复的节点，接着从以cur.next为首的子链表中找出与cur有着相同的数据域的节点并删除。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //对以head.next为首的子链表删除重复的节点
        head.next = deleteDuplicates(head.next);
        //找出以head.next为首的子链表中与head节点相同的节点并删除
        if(head.val == head.next.val){
            head = head.next;//此处直接切换头节点是最好的选择
        }   
        return head;
    }
}