数据结构之链表及java实现（二）

上次的尾巴，实现合并两个有序的链表的递归方法：

思路：

• 比较两个链表头结点的值，较小的就可以挪出，然后剩下的比较，合并即可。
• 每次的返回值，是排序好 的链表头。

public ListNode MergeRec(ListNode list1,ListNode list2){
        if(list1==null&&list2==null){
            return null;
        }
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        if(list2.val>list1.val){
            list1.next=MergeRec(list1.next,list2);
            return list1;
        }else {
            list2.next=MergeRec(list1,list2.next);
            return list2;
        }
    }

其实理清头绪这个问题还是so easy的，我想了一下上次写不出来的原因还是没有搞明白链表的本质内容，说通俗一点其实它就是一个穿针引线，当你反复在纸上画图，画引用，之后的某一时刻，你就会豁然开朗吧！（至于图具体怎么画我就不详细演示了，不然那样会显得我的文章很没有气质！！！！！！）

最后如果对于链表还有不清楚地方的童鞋，我之后会在资源区上传一份“傻瓜”版的教程（就是基本每一行代码的来龙去脉都有详细解释，还包含测试的输入与输出的那种）。

接下来我会开始总结一些关于链表的具体题型：

我们很容易想到的思路就是，先把它保存在一个中间List中，然后倒序（i–)获取元素，进一步存入到新的List中，返回结果即可。但其实这种反转我们可以想到栈，栈的特点就是先进后出，所以完全可以先遍历节点以及入栈，再一个一个弹出栈，再将节点添加到list集合中进行返回即可。

    public ArrayList printListFromTailToHead(ListNode listNode) {
        //提前返回结果
        if(listNode==null){
            return new ArrayList();
        }
        if (listNode.next==null){
            return new ArrayList(listNode.val);
        }
        Stack stack = new Stack<>();
        ListNode currentNode = listNode;
        //入栈
        while (currentNode!=null){
            stack.push(currentNode.val);
            currentNode=currentNode.next;
        }
        //出栈
        ArrayList list = new ArrayList<>();
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }

例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

这题乍一看好像是挺简单的，但仔细一看还真挺难的，而且还是要指向这儿指向那儿的链表，最主要是要完全删除重复的结点，真是完全晕乎了，我是参考了题解的思路：

• 多次遍历，第一次遍历把重复的结点值存入 set 容器，第二次遍历，当结点值存储在 set 容器中，就删除该结点

public class Solution {
    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null){
            return  null;
        }
        // 先找出相同结点，存入 set
        HashSet set = new HashSet<>();
        ListNode pre = pHead;
        ListNode cur = pHead.next;
        while(cur != null){
            if(cur.val == pre.val){
                set.add(cur.val);
            }
            pre = cur;
            cur = cur.next;
        }
        // 再根据相同节点删除
        // 先删头部
        while(pHead != null && set.contains(pHead.val)){
            pHead = pHead.next;
        }
        if(pHead == null){
            return null;
        }
        // 再删中间结点
        pre = pHead;
        cur = pHead.next;
        while(cur != null){
            if(set.contains(cur.val)){
                pre.next = cur.next;
                cur = cur.next;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return pHead;
    }
}

• HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

• HashSet 允许有 null 值。

• HashSet 是无序的，即不会记录插入的顺序。

import java.util.HashSet; // 引入 HashSet 类
HashSet sites = new HashSet();//实例化
//添加元素
public class RunoobTest {
    public static void main(String[] args) {
    HashSet sites = new HashSet();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");  // 重复的元素不会被添加
        System.out.println(sites);
    }
}
//结果：[Google, Runoob, Zhihu, Taobao]
//使用 contains() 方法判断元素是否存在
public class RunoobTest {
    public static void main(String[] args) {
    HashSet sites = new HashSet();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");  // 重复的元素不会被添加
        System.out.println(sites.contains("Taobao"));
    }
}
//结果：true
//使用 remove() 方法来删除集合中的元素
public class RunoobTest {
    public static void main(String[] args) {
    HashSet sites = new HashSet();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");     // 重复的元素不会被添加
        sites.remove("Taobao");  // 删除元素，删除成功返回 true，否则为 false
        System.out.println(sites);
    }
}
//[Google, Runoob, Zhihu]
//删除集合中所有元素可以使用 clear 方法
public class RunoobTest {
    public static void main(String[] args) {
    HashSet sites = new HashSet();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");     // 重复的元素不会被添加
        sites.clear();  
        System.out.println(sites);
    }
}
//如果要计算 HashSet 中的元素数量可以使用 size() 方法
 public class RunoobTest {
    public static void main(String[] args) {
    HashSet sites = new HashSet();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");     // 重复的元素不会被添加
        System.out.println(sites.size());  
    }
}
//4
//可以使用 for-each 来迭代 HashSet 中的元素
public class RunoobTest {
    public static void main(String[] args) {
    HashSet sites = new HashSet();
        sites.add("Google");
        sites.add("Runoob");
        sites.add("Taobao");
        sites.add("Zhihu");
        sites.add("Runoob");     // 重复的元素不会被添加
        for (String i : sites) {
            System.out.println(i);
        }
    }
}
//Google
//Runoob
//Zhihu
//Taobao

判断链表中是否存在环

可以利用HashSet不可重复的特性

    public boolean CycleList(ListNode head) {
        if(head == null){
            return false;
        }
        Set set = new HashSet();
        while (head.next!=null){
            if (!set.add(head)) {//判断set中是否有该结点
                return true;//证明有环存在
            }
            head=head.next;
        }
        return false;//证明无环存在
    }

----《侧脸》于果

曾经是心心念念
随随便便深深浅浅
爱上了不语不言不计前嫌不知疲倦
向后向前遇见改变